Quantum search for scaled hash function preimages
| Autor: | Emanuele Bellini, Sergi Ramos-Calderer, Victor Mateu, José I. Latorre, Marc Manzano |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Quantum register
Computer science Hash function Quantum simulator Statistical and Nonlinear Physics Quantum entanglement Theoretical Computer Science Electronic Optical and Magnetic Materials Quantum circuit Modeling and Simulation Signal Processing Grover's algorithm Electrical and Electronic Engineering Bitwise operation Algorithm Quantum computer |
| Zdroj: | Quantum Information Processing. 20 |
| ISSN: | 1573-1332 1570-0755 |
| Popis: | We present the implementation of Grover’s algorithm in a quantum simulator to perform a quantum search for preimages of two scaled hash functions, whose design only uses modular addition, word rotation and bitwise exclusive or. Our implementation provides the means to assess with precision the scaling of the number of gates and depth of a full-fledged quantum circuit designed to find the preimages of a given hash digest. The detailed construction of the quantum oracle shows that the presence of AND gates, OR gates, shifts of bits and the reuse of the initial state along the computation require extra quantum resources as compared with other hash functions based on modular additions, XOR gates and rotations. We also track the entanglement entropy present in the quantum register at every step along the computation, showing that it becomes maximal at the inner core of the first action of the quantum oracle, which implies that no classical simulation based on tensor networks would be of relevance. Finally, we show that strategies that suggest a shortcut based on sampling the quantum register after a few steps of Grover’s algorithm can only provide some marginal practical advantage in terms of error mitigation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink