Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1702.02577 · Physical Review A

Near-optimal quantum circuit for Grover's unstructured search using a transverse field

Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang

Published Jun 12, 2017• 143 citations
arXivHTMLPDF

Abstract

Inspired by a class of algorithms proposed by Farhi et al. (arXiv:1411.4028), namely, the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduce a technique, based on spin-coherent states, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order $\mathrm{\ensuremath{\Theta}}(1/\sqrt{N})$, and the overlaps are of order $\mathrm{\ensuremath{\Theta}}(1)$, yielding a nearly optimal query complexity of $T\ensuremath{\simeq}\sqrt{N}\phantom{\rule{0.4pt}{0ex}}(\ensuremath{\pi}/2\sqrt{2})$. Our algorithm is a QAOA circuit that demonstrates a quantum advantage with a large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.

DOI
10.1103/physreva.95.062317

Related papers

A QAOA-inspired circuit for Grover's unstructured search using a transverse field

Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang

Inspired by a class of algorithms proposed by Farhi et al., namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduced a novel technique, a spin-coherent-state approach, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order $\Theta(1/\sqrt N)$, and the overlaps are of order $\Theta(1)$, yielding a nearly optimal query complexity of $T\simeq \sqrt N (\pi/2\sqrt 2\,)$. Our algorithm is the first example of a QAOA circuit that demonstrates a quantum advantage with large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.

•Feb 8, 2017•4 citations

A Circuit-Based Quantum Algorithm Driven by Transverse Fields for Grover's Problem

Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang

We designed a quantum search algorithm, giving the same quadratic speedup achieved by Grover's original algorithm; we replace Grover's diffusion operator (hard to implement) with a product diffusion operator generated by transverse fields (easy to implement). In our algorithm, the problem Hamiltonian (oracle) and the transverse fields are applied to the system alternatively. We construct such a sequence that the corresponding unitary generates a closed transition between the initial state (even superposition of all states) and a modified target state, which has a high degree of overlap with the original target state.

•Jan 1, 2017•0 citations

Depth scaling of unstructured search via quantum approximate optimization

Ernesto Campos, Daniil Rabinovich, Alexey Uvarov

Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms---the quantum approximate optimization algorithm (QAOA)---was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity $O({N}^{\frac{1}{2}})$, but remains smaller than $O({N}^{\frac{1}{2}+c})$ for any $c>0$, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.

arXiv:2403.15540•Physical Review A•Jul 9, 2024•3 citations

Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth

Murphy Yuezhen Niu, Sirui Lu, Isaac L. Chuang

The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies on p in both low and large p limits by leveraging the unique spectral property of the XY Hamiltonian. We support our proof under a given QAOA ansatz with numerical optimizations of QAOA for up to \(N\)=20 qubits. We show that the optimized QAOA can achieve the well-known quadratic speedup, Grover speedup, over the classical alternatives. Treating QAOA optimization as a quantum control problem, we also provide numerical evidence of how the circuit depth determines the controllability of the QAOA ansatz.

arXiv:1905.12134•May 28, 2019•23 citations

Test-state approach to the quantum search problem

Arun Sehrawat, Le Huy Nguyen, Berthold‐Georg Englert

The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.

arXiv:1102.3628•Physical Review A•May 17, 2011•5 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•6 citations
Inspired by a class of algorithms proposed by Farhi et al. (arXiv:1411.4028), namely, the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduce a technique, based on spin-coherent states, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order \ensuremathΘ(1/N)\mathrm{\ensuremath{\Theta}}(1/\sqrt{N})\ensuremathΘ(1/N​), and the overlaps are of order \ensuremathΘ(1)\mathrm{\ensuremath{\Theta}}(1)\ensuremathΘ(1), yielding a nearly optimal query complexity of T\ensuremath≃N(\ensuremathπ/22)T\ensuremath{\simeq}\sqrt{N}\phantom{\rule{0.4pt}{0ex}}(\ensuremath{\pi}/2\sqrt{2})T\ensuremath≃N​(\ensuremathπ/22​). Our algorithm is a QAOA circuit that demonstrates a quantum advantage with a large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.
Inspired by a class of algorithms proposed by Farhi et al., namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduced a novel technique, a spin-coherent-state approach, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order Θ(1/N)\Theta(1/\sqrt N)Θ(1/N​), and the overlaps are of order Θ(1)\Theta(1)Θ(1), yielding a nearly optimal query complexity of T≃N(π/22 )T\simeq \sqrt N (\pi/2\sqrt 2\,)T≃N​(π/22​). Our algorithm is the first example of a QAOA circuit that demonstrates a quantum advantage with large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.
We designed a quantum search algorithm, giving the same quadratic speedup achieved by Grover's original algorithm; we replace Grover's diffusion operator (hard to implement) with a product diffusion operator generated by transverse fields (easy to implement). In our algorithm, the problem Hamiltonian (oracle) and the transverse fields are applied to the system alternatively. We construct such a sequence that the corresponding unitary generates a closed transition between the initial state (even superposition of all states) and a modified target state, which has a high degree of overlap with the original target state.
Variational quantum algorithms have become the de facto model for current quantum computations. A prominent example of such algorithms---the quantum approximate optimization algorithm (QAOA)---was originally designed for combinatorial optimization tasks, but has been shown to be successful for a variety of other problems. However, for most of these problems the optimal circuit depth remains unknown. One such problem is unstructured search, which consists of finding a particular bit string or, equivalently, preparing a state of high overlap with a target state. To bound the optimal QAOA depth for such a problem we build on its known solution in a continuous time quantum walk (CTQW). We Trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity (circuit depth) needed to prepare a state that approaches perfect overlap with the target state. The obtained complexity exceeds Grover's algorithm complexity O(N12)O({N}^{\frac{1}{2}})O(N21​), but remains smaller than O(N12+c)O({N}^{\frac{1}{2}+c})O(N21​+c) for any c>0c>0c>0, which shows quantum advantage of QAOA over classical solutions. We verify our analytical predictions by numerical simulations of up to 68 qubits.
The quantum approximate optimization algorithm~(QAOA) first proposed by Farhi et al. promises near-term applications based on its simplicity, universality, and provable optimality. A depth-p QAOA consists of p interleaved unitary transformations induced by two mutually non-commuting Hamiltonians. A long-standing question concerning the performance of QAOA is the dependence of its success probability as a function of circuit depth p. We make initial progress by analyzing the success probability of QAOA for realizing state transfer in a one-dimensional qubit chain using two-qubit XY Hamiltonians and single-qubit Hamiltonians. We provide analytic state transfer success probability dependencies on p in both low and large p limits by leveraging the unique spectral property of the XY Hamiltonian. We support our proof under a given QAOA ansatz with numerical optimizations of QAOA for up to NNN=20 qubits. We show that the optimized QAOA can achieve the well-known quadratic speedup, Grover speedup, over the classical alternatives. Treating QAOA optimization as a quantum control problem, we also provide numerical evidence of how the circuit depth determines the controllability of the QAOA ansatz.
The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.