Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Improved Low-qubit Hidden Shift Algorithms

Abstract : Hidden shift problems are relevant to assess the quantum security of various cryptographic constructs. Multiple quantum subexponential time algorithms have been proposed. In this paper, we propose some improvements on a polynomial quantum memory algorithm proposed by Childs, Jao and Soukharev in 2010. We use subset-sum algorithms to significantly reduce its complexity. We also propose new tradeoffs between quantum queries, classical time and classical memory to solve this problem.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-02400414
Contributor : Xavier Bonnetain <>
Submitted on : Monday, December 9, 2019 - 2:47:11 PM
Last modification on : Tuesday, December 17, 2019 - 2:27:43 AM
Long-term archiving on: : Tuesday, March 10, 2020 - 9:52:24 PM

File

1901.11428.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02400414, version 1
  • ARXIV : 1901.11428

Collections

Citation

Xavier Bonnetain. Improved Low-qubit Hidden Shift Algorithms. 2019. ⟨hal-02400414⟩

Share

Metrics

Record views

25

Files downloads

47