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:2403.15540 · Physical Review A

Depth scaling of unstructured search via quantum approximate optimization

Ernesto Campos, Daniil Rabinovich, Alexey Uvarov

Published Jul 9, 2024• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.110.012428

Related papers

Near-optimal quantum 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. (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.

arXiv:1702.02577•Physical Review A•Jun 12, 2017•143 citations

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

Circuit depth scaling for quantum approximate optimization

V. Akshay, Hariphan Philathong, Ernesto Campos +4 more

Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density---a problem constraint to a variable ratio---induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\ensuremath{\sigma}$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5--15 qubits.

arXiv:2205.01698•Physical Review A•Oct 25, 2022•21 citations

Variational Quantum Search with Shallow Depth for Unstructured Database Search

Junpeng Zhan

Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.

arXiv:2212.09505•Dec 22, 2023•4 citations

Shallow-Depth Quantum Circuit for Unstructured Database Search

Junpeng Zhan

Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits.

Quantum Reports•Oct 25, 2024•0 citations

A Depth-Progressive Initialization Strategy for Quantum Approximate Optimization Algorithm

Xinwei Lee, Ningyi Xie, Dongsheng Cai +2 more

The quantum approximate optimization algorithm (QAOA) is known for its capability and universality in solving combinatorial optimization problems on near-term quantum devices. The results yielded by QAOA depend strongly on its initial variational parameters. Hence, parameter selection for QAOA becomes an active area of research, as bad initialization might deteriorate the quality of the results, especially at great circuit depths. We first discuss the patterns of optimal parameters in QAOA in two directions: the angle index and the circuit depth. Then, we discuss the symmetries and periodicity of the expectation that is used to determine the bounds of the search space. Based on the patterns in optimal parameters and the bounds restriction, we propose a strategy that predicts the new initial parameters by taking the difference between the previous optimal parameters. Unlike most other strategies, the strategy we propose does not require multiple trials to ensure success. It only requires one prediction when progressing to the next depth. We compare this strategy with our previously proposed strategy and the layerwise strategy for solving the Max-cut problem in terms of the approximation ratio and the optimization cost. We also address the non-optimality in previous parameters, which is seldom discussed in other works despite its importance in explaining the behavior of variational quantum algorithms.

arXiv:2209.11348•Mathematics•May 5, 2023•20 citations
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.
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.
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.
Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density---a problem constraint to a variable ratio---induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a $3\ensuremath{\sigma}$ confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5--15 qubits.
Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.
Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits.
The quantum approximate optimization algorithm (QAOA) is known for its capability and universality in solving combinatorial optimization problems on near-term quantum devices. The results yielded by QAOA depend strongly on its initial variational parameters. Hence, parameter selection for QAOA becomes an active area of research, as bad initialization might deteriorate the quality of the results, especially at great circuit depths. We first discuss the patterns of optimal parameters in QAOA in two directions: the angle index and the circuit depth. Then, we discuss the symmetries and periodicity of the expectation that is used to determine the bounds of the search space. Based on the patterns in optimal parameters and the bounds restriction, we propose a strategy that predicts the new initial parameters by taking the difference between the previous optimal parameters. Unlike most other strategies, the strategy we propose does not require multiple trials to ensure success. It only requires one prediction when progressing to the next depth. We compare this strategy with our previously proposed strategy and the layerwise strategy for solving the Max-cut problem in terms of the approximation ratio and the optimization cost. We also address the non-optimality in previous parameters, which is seldom discussed in other works despite its importance in explaining the behavior of variational quantum algorithms.