Variationally Learning Grover's Quantum Search Algorithm
arXiv:1805.09337 · doi:10.1103/PhysRevA.98.062333
Abstract
Given a parameterized quantum circuit such that a certain setting of these real-valued parameters corresponds to Grover's celebrated search algorithm, can a variational algorithm recover these settings and hence learn Grover's algorithm? We studied several constrained variations of this problem and answered this question in the affirmative, with some caveats. Grover's quantum search algorithm is optimal up to a constant. The success probability of Grover's algorithm goes from unity for two-qubits, decreases for three- and four-qubits and returns near unity for five-qubits then oscillates ever-so-close to unity, reaching unity in the infinite qubit limit. The variationally approach employed here found an experimentally discernible improvement of and for three- and four-qubits respectively. Our findings are interesting as an extreme example of variational search, and illustrate the promise of using hybrid quantum classical approaches to improve quantum algorithms. This paper further demonstrates that to find optimal parameters one doesn't need to vary over a family of quantum circuits to find an optimal solution. This result looks promising and points out that there is a set of variational quantum problems with parameters that can be efficiently found on a classical computer for arbitrary number of qubits.
arXiv commentAccepted version (PRA); All supporting data and source code are available online; 8 pages; 4 figures; RevTeX
References in corpus (23)
- A variational eigenvalue solver on a quantum processor
- Elementary gates for quantum computation
- Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms
- The theory of variational hybrid quantum-classical algorithms
- A Quantum Approximate Optimization Algorithm
- Strengths and Weaknesses of Quantum Computing
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum optimization using variational algorithms on near-term quantum devices
- Grover's quantum searching algorithm is optimal
- Quantum Search by Local Adiabatic Evolution
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Learning the quantum algorithm for state overlap
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
- Unsupervised Machine Learning on a Hybrid Quantum Computer
- On Arbitrary Phases in Quantum Amplitude Amplification
- Phase matching in quantum searching
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- A quantum algorithm to train neural networks using low-depth circuits
- Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm
- A General Phase Matching Condition for Quantum Searching Algorithm
- A Grover-based quantum search of optimal order for an unknown number of marked elements
- Learning Simon's quantum algorithm
Cited by in corpus (31)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Parameterized quantum circuits as machine learning models
- Continuous-variable quantum neural networks
- Reachability Deficits in Quantum Approximate Optimization
- Large gradients via correlation in random parameterized quantum circuits
- On barren plateaus and cost function locality in variational quantum algorithms
- Quantum neuromorphic computing
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Depth optimization of quantum search algorithms beyond Grover's algorithm
- A Grover-search Based Quantum Learning Scheme for Classification
- Number Partitioning with Grover's Algorithm in Central Spin Systems
- 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 Machine Learning Tensor Network States
- Quantum Amplitude Amplification Operators
- Deterministic spatial search using alternating quantum walks
- Variational Quantum Cloning: Improving Practicality for Quantum Cryptanalysis
- Fair Sampling Error Analysis on NISQ Devices
- A Continuous Variable Born Machine
- Ion native variational ansatz for quantum approximate optimization
- Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
- Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
- Amplitude Amplification for Optimization via Subdivided Phase Oracle
- Optimization of probabilistic quantum search algorithm with a priori information
- Enhancing Grover's Search Algorithm: A Modified Approach to Increase the Probability of Good States
- Depth scaling of unstructured search via quantum approximate optimization
- Near-deterministic quantum search algorithm without phase design
- Grover's search meets Ising models: a quantum algorithm for finding low-energy states
- Variational quantum cloning machine on an integrated photonic interferometer