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

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 $\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 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 comment9 pages, 4 figures

References in corpus (12)

• A Quantum Approximate Optimization Algorithm
• Strengths and Weaknesses of Quantum Computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Periodically-driven quantum systems: Effective Hamiltonians and engineered gauge fields
• Grover's quantum searching algorithm is optimal
• Quantum Search by Local Adiabatic Evolution
• Quantum Computation by Adiabatic Evolution
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Training A Quantum Optimizer
• Unification and limitations of error suppression techniques for adiabatic quantum computing
• Error suppression and error correction in adiabatic quantum computation I: techniques and challenges

Cited by in corpus (77)

• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• $XY$-mixers: analytical and numerical results for QAOA
• Reachability Deficits in Quantum Approximate Optimization
• Large gradients via correlation in random parameterized quantum circuits
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Parameter Concentration in Quantum Approximate Optimization
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Scalable algorithm simplification using quantum AND logic
• Empirical performance bounds for quantum approximate optimization
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Variationally Learning Grover's Quantum Search Algorithm
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Implementation of efficient quantum search algorithms on NISQ computers
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• An entanglement perspective on the quantum approximate optimization algorithm
• Quantum approximate optimization algorithm for qudit systems
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Analytical Framework for Quantum Alternating Operator Ansätze
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Threshold-Based Quantum Optimization
• Quantum Optimization for Training Quantum Neural Networks
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Deterministic spatial search using alternating quantum walks
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Quantum Approximate Optimization Algorithm for Test Case Optimization
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Asymptotic optimality of twist-untwist protocols for Heisenberg scaling in atomic interferometry
• Progress towards analytically optimal angles in quantum approximate optimisation
• Approximating under the Influence of Quantum Noise and Compute Power
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Hardware Efficient Quantum Search Algorithm
• Ion native variational ansatz for quantum approximate optimization
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Forbidden subspaces for level-1 QAOA and IQP circuits
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Self-protected adiabatic quantum computation
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Depth scaling of unstructured search via quantum approximate optimization
• Near-deterministic quantum search algorithm without phase design
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers
• Globally optimal interferometry with lossy twin Fock probes
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• A loop Quantum Approximate Optimization Algorithm with Hamiltonian updating
• Enhanced Framework of Quantum Approximate Optimization Algorithm and Its Parameter Setting Strategy