$T$-depth-optimized Quantum Search with Quantum Data-access Machine
- URL: http://arxiv.org/abs/2211.03941v2
- Date: Thu, 2 Nov 2023 23:37:42 GMT
- Title: $T$-depth-optimized Quantum Search with Quantum Data-access Machine
- Authors: Jung Jun Park, Kyunghyun Baek, M. S. Kim, Hyunchul Nha, Jaewan Kim,
and Jeongho Bang
- Abstract summary: We introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM)
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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- 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.
Related papers
- Compression of quantum shallow-circuit states [11.305910458469098]
Storing quantum information generated by shallow circuits is a fundamental question of both theoretical and practical importance.
We show that $N$ copies of an unknown $n$-qubit state can be compressed into a hybrid memory of $O(n log N)$ (qu)bits.
arXiv Detail & Related papers (2024-04-17T08:48:07Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits.
It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness.
Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
arXiv Detail & Related papers (2024-01-10T22:33:00Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - QArchSearch: A Scalable Quantum Architecture Search Package [1.725192300740999]
We present textttQArchSearch, an AI based quantum architecture search package with the textttQTensor library as a backend.
We show that the search package is able to efficiently scale the search to large quantum circuits and enables the exploration of more complex models for different quantum applications.
arXiv Detail & Related papers (2023-10-11T20:00:33Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCS aims at index searching and counting in a quantum-classical hybrid system.
We implement IQuCS with Qiskit and conduct intensive experiments.
Results demonstrate that it reduces qubits consumption by up to 66.2%.
arXiv Detail & Related papers (2022-09-22T21:54:28Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
We show that classical algorithms with sample and query (SQ) access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs.
Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs.
arXiv Detail & Related papers (2021-12-01T20:05:56Z) - $i$-QER: An Intelligent Approach towards Quantum Error Reduction [5.055934439032756]
We introduce $i$-QER, a scalable machine learning-based approach to evaluate errors in a quantum circuit.
The $i$-QER predicts possible errors in a given quantum circuit using supervised learning models.
It cuts the large quantum circuit into two smaller sub-circuits using an error-influenced fragmentation strategy.
arXiv Detail & Related papers (2021-10-12T20:45:03Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.