Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
arXiv:1908.09886 · doi:10.1103/PhysRevA.100.022327
Abstract
Grover's algorithm is one of the most famous algorithms which explicitly demonstrates how the quantum nature can be utilized to accelerate the searching process. In this work, Grover's quantum search problem is mapped to a time-optimal control problem. Resorting to Pontryagin's Minimum Principle we find that the time-optimal solution has the bang-singular-bang structure. This structure can be derived naturally, without integrating the differential equations, using the geometric control technique where Hamiltonians in the Schrödinger's equation are represented as vector fields. In view of optimal control, Grover's algorithm uses the bang-bang protocol to approximate the optimal protocol with a minimized number of bang-to-bang switchings to reduce the query complexity. Our work provides a concrete example how Pontryagin's Minimum Principle is connected to quantum computation, and offers insight into how a quantum algorithm can be designed.
arXiv comment4 figures
References in corpus (29)
- Quantum Computing in the NISQ era and beyond
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A variational eigenvalue solver on a quantum processor
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum algorithm for solving linear systems of equations
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A Quantum Approximate Optimization Algorithm
- Strengths and Weaknesses of Quantum Computing
- Scalable Quantum Simulation of Molecular Energies
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Towards Practical Quantum Variational Algorithms
- Quantum Annealing and Analog Quantum Computation
- Quantum Search by Local Adiabatic Evolution
- Quantum Computation by Adiabatic Evolution
- Reinforcement Learning in Different Phases of Quantum Control
- Quantum versus Classical Annealing of Ising Spin Glasses
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Quantum Adiabatic Brachistochrone
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Training A Quantum Optimizer
- Glassy Phase of Optimal Quantum Control
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- The fastest pulses that implement dynamically corrected gates
- Optimal control of superconducting gmon qubits using Pontryagin's minimum principle: preparing a maximally entangled state with singular bang-bang protocols
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree
- Quantum imaging by coherent enhancement
Cited by in corpus (19)
- Introduction to the Pontryagin Maximum Principle for Quantum Optimal Control
- Differentiable Quantum Architecture Search
- Optimal Protocols in Quantum Annealing and QAOA Problems
- From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
- Optimal Control for Quantum Metrology via Pontryagin's principle
- Time-optimal control of a dissipative qubit
- Optimal Control for Closed and Open System Quantum Optimization
- Binary Control Pulse Optimization for Quantum Systems
- Stochastic optimal control formalism for an open quantum system
- State preparation of lattice field theories using quantum optimal control
- Minimizing state preparation times in pulse-level variational molecular simulations
- Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
- Algorithmic Primitives for Quantum-Assisted Quantum Control
- Switching Time Optimization for Binary Quantum Optimal Control
- Optimal solutions to quantum annealing using two independent control functions
- Fighting Exponentially Small Gaps by Counterdiabatic Driving
- Time-Optimal Two- and Three-Qubit Gates for Rydberg Atoms
- Time-optimal single-scalar control on a qubit of unitary dynamics
- CDJ-Pontryagin Optimal Control for General Continuously Monitored Quantum Systems