Optimizing a Polynomial Function on a Quantum Simulator

Abstract

Gradient descent method, as one of the major methods in numerical optimization, is the key ingredient in many machine learning algorithms. As one of the most fundamental way to solve the optimization problems, it promises the function value to move along the direction of steepest descent. For the vast resource consumption when dealing with high-dimensional problems, a quantum version of this iterative optimization algorithm has been proposed recently[arXiv:1612.01789]. Here, we develop this protocol and implement it on a quantum simulator with limited resource. Moreover, a prototypical experiment was shown with a 4-qubit Nuclear Magnetic Resonance quantum processor, demonstrating a optimization process of polynomial function iteratively. In each iteration, we achieved an average fidelity of 94\% compared with theoretical calculation via full-state tomography. In particular, the iterative point gradually converged to the local minimum. We apply our method to multidimensional scaling problem, further showing the potentially capability to yields an exponentially improvement compared with classical counterparts. With the onrushing tendency of quantum information, our work could provide a subroutine for the application of future practical quantum computers.

6+4 pages, 8 figures

References in corpus (17)

• Quantum Computing
• Quantum algorithm for solving linear systems of equations
• NMR Techniques for Quantum Control and Computation
• Evaluating analytic gradients on quantum hardware
• Quantum random access memory
• Architectures for a quantum random access memory
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• Soundness and completeness of quantum root-mean-square errors
• The General Quantum Interference Principle and the Duality Computer
• A quantum linear system algorithm for dense matrices
• Quantum gradient descent for linear systems and least squares
• Iterative algorithm for reconstruction of entangled states
• On the robustness of bucket brigade quantum RAM
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Insensitive Stochastic Gradient Twin Support Vector Machine for Large Scale Problems
• Quantum simulation of quantum channels in nuclear magnetic resonance

Cited by in corpus (8)

• Challenges and Opportunities in Quantum Optimization
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Quantum algorithms for the generalized eigenvalue problem
• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Controlling NMR spin systems for quantum computation
• Quantum Langevin Dynamics for Optimization
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Improved iterative quantum algorithm for ground-state preparation