Lagrangian duality and Adiabatic quantum computation for constrained optimization problems

The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic method for solving unconstrained binary optimization problems with a gate-based quantum computer. The QAOA consists of a particular quantum circuit architecture, together with a prescription for choosing the parameterization of the circuit. The first part of the thesis studies both the architecture and optimal parameterization of the QAOA circuit. After reviewing the necessary mathematical and physical background, we derive QAOA from scratch and discuss some of its properties. The second part of the thesis focuses on solving constrained combinatorial optimization problems in the setting of fault-tolerant quantum computation and presents a novel Lagrangian duality approach to Discretized Adiabatic Quantum Computation (DAQC). The proposed method allows for building highly resource-efficient and parallelizable quantum circuits. The thesis presents numerical evidence that demonstrates that the proposed approach gives the quadratic improvement in circuit complexity and evolution time over circuits derived from the traditional Quadratic Unconstrained Binary Optimization (QUBO) formalism. We illustrate our findings in the benchmark of the QUBO- and Lagrangian-based DAQC on the NP-complete 1D 0-1 knapsack problem.