$T$-depth-optimized Quantum Search with Quantum Data-access Machine

Abstract

Quantum search algorithms offer a remarkable advantage of quadratic reduction in query complexity using quantum superposition principle. However, how an actual architecture may access and handle the database in a quantum superposed state has been largely unexplored so far; the quantum state of data was simply assumed to be prepared and accessed by a black-box operation -- so-called oracle, even though this process, if not appropriately designed, may adversely diminish the quantum query advantage. Here, we introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM), and present a general architecture for quantum search algorithm. We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code. Specifically, we introduce a measure involving two computational complexities, i.e. quantum query and $T$-depth complexities, which can be critical to assess performance since the logical non-Clifford gates, such as the $T$ (i.e., $\pi /8$ rotation) gate, are known to be costliest to implement in FTQC. Our analysis shows that for $N$ searching data, a QDAM model exhibiting a logarithmic, i.e., $O(\log N)$, growth of the $T$-depth complexity can be constructed. Further analysis reveals that our QDAM-embedded quantum search requires $O(\sqrt{N}\times \log N)$ runtime cost. Our study thus demonstrates that the quantum data search algorithm can truly speed up over classical approaches with the logarithmic $T$-depth QDAM as a key component.

arXiv comment16 pages, 8 figures / Published version

References in corpus (19)

• Quantum Mechanics helps in searching for a needle in a haystack
• Surface codes: Towards practical large-scale quantum computation
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum Amplitude Amplification and Estimation
• Grover's quantum searching algorithm is optimal
• Surface code quantum computing by lattice surgery
• Restrictions on Transversal Encoded Quantum Gate Sets
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum circuits of T-depth one
• Phase matching in quantum searching
• Circuit-Based Quantum Random Access Memory for Classical Data
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Engineering of arbitrary U(N) transformations by quantum Householder reflections
• Parallelizing quantum circuit synthesis
• Grover search and the no-signaling principle
• A General Phase Matching Condition for Quantum Searching Algorithm
• Quantum search of a real unstructured database
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation

Cited by in corpus (1)

• QRAM: A Survey and Critique