Quantum Algorithms for Scientific Computing and Approximate Optimization

Abstract

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we consider the application of quantum computers to scientific computing and combinatorial optimization. We study five problems. The first three deal with quantum algorithms for computational problems in science and engineering, including quantum simulation of physical systems. In particular, we study quantum algorithms for numerical computation, for the approximation of ground and excited state energies of the Schrödinger equation, and for Hamiltonian simulation with applications to physics and chemistry. The remaining two deal with quantum algorithms for approximate optimization. We study the performance of the quantum approximate optimization algorithm (QAOA), and show a generalization of QAOA, the $\text{quantum}$ $\text{alternating}$ $\text{operator}$ $\text{ansatz}$, particularly suitable for constrained optimization problems and low-resource implementations on near-term quantum devices.

264 pages, 20 figures. PhD Dissertation in Computer Science, Columbia University (2018). Abstract shortened for arXiv

Cited by in corpus (18)

• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Quantum Computing: Towards Industry Reference Problems
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Analytical Framework for Quantum Alternating Operator Ansätze
• Approximating the quantum approximate optimization algorithm with digital-analog interactions
• Approaches to Constrained Quantum Approximate Optimization
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization
• Synergies Between Operations Research and Quantum Information Science
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• A Universal Quantum Circuit Design for Periodical Functions
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Quantum algorithmic differentiation