Improved Low-qubit Hidden Shift Algorithms - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Improved Low-qubit Hidden Shift Algorithms

(1)
1
Xavier Bonnetain
  • Function : Author
  • PersonId : 1023884

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.
Fichier principal
Vignette du fichier
1901.11428.pdf (174.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02400414 , version 1 (09-12-2019)

Identifiers

Cite

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

Collections

INRIA INRIA2
27 View
39 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More