Skip to main content

Lagrangian duality and Adiabatic quantum computation for constrained optimization problems

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2022-08-09
Authors/Contributors
Abstract
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.
Document
Extent
72 pages.
Identifier
etd22037
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Adcock, Ben
Language
English
Member of collection
Download file Size
etd22037.pdf 4.05 MB

Views & downloads - as of June 2023

Views: 76
Downloads: 4