Mon, Dec 19, 2022 @ 09:00 AM - 11:00 PM
Thomas Lord Department of Computer Science
Committee: Greg ver Steeg, Federico M. Spedalieri, Aiichiro Nakano, and Todd A. Brun
Title: Imposing Classical Symmetries on Quantum Operators with Applications to Optimization
Applying quantum computers to solve combinatorial optimization tasks is one of the most exciting ways to leverage quantum systems for practical computational advantage. Two of the primary paradigms to leverage NISQ quantum computers for such tasks are Quantum Annealing (QA) and the Quantum Alternating Operator Ansatz (QAOA). A typical approach for both would be to map a combinatorial optimization problem with feasibility constraints to an unconstrained quadratic optimization problem. However, it is possible to impose these constraints on the evolution of the quantum system by selecting the quantum operators applied to the system such that the corresponding observables remain invariant under the evolution of the quantum state. We consider such approaches to be imposing classical symmetries on the quantum operators. As such, the task of finding such Hamiltonians or unitaries for a collection of constraints is an important task for tailoring quantum algorithms to optimization problems with feasibility constraints.
In this thesis, we give an algebraic formulation for imposing an arbitrary collection of constraint symmetries on quantum operators. This allows us to describe a general algorithm to solve the corresponding task for linear constraints in polynomial time for bounded weight operators and classify the complexity of several related computational problems.
We then consider a quantum annealing protocol for the problem of combinational circuit fault diagnostics (CCFD) and analyze features of our approach that make it attractive for quantum annealers built to solve this class of combinatorial optimization problems. Next, we consider several QAOA protocols that are tailored to impose different constraint symmetries underlying this problem and study the trade-offs between the protocols. Our results are consistent with the view that tailoring the ansatz of a protocol to match the underlying symmetry of an optimization problem can be benefical to finding solutions with a lower QAOA depth under several parameter optimization schemes.
WebCast Link: https://usc.zoom.us/j/93517166738
Audiences: Everyone Is Invited
Contact: Lizsl De Leon