Constraints make hard optimization problems even harder to solve on quantum devices because they are implemented with large energy penalties and additional qubit overhead. The parity mapping, which has been introduced as an alternative to the spin encoding, translates the problem to a representation using only parity variables that encodes products of spin variables. In combining exchange interaction and single spin flip terms in the parity representation, constraints on sums and products of arbitrary k -body terms can be implemented without additional overhead in two-dimensional quantum systems.
Constraints make hard optimization problems even harder to solve on quantum devices because they are implemented with large energy penalties and additional qubit overhead. The parity mapping, which has been introduced as an alternative to the spin encoding, translates the problem to a representation using only parity variables that encodes products of spin variables. In combining exchange interaction and single spin flip terms in the parity representation, constraints on sums and products of arbitrary k -body terms can be implemented without additional overhead in two-dimensional quantum systems.
We introduce parity quantum optimization with the aim of solving optimization problems consisting of arbitrary k -body interactions and side conditions using planar quantum chip architectures. The method introduces a decomposition of the problem graph with arbitrary k -body terms using generalized closed cycles of a hypergraph. Side conditions of the optimization problem in form of hard constraints can be included as open cycles containing the terms involved in the side conditions. The generalized parity mapping thus circumvents the need to translate optimization problems to a quadratic unconstrained binary optimization problem (QUBO) and allows for the direct encoding of higher-order constrained binary optimization problems (HCBO) on a square lattice and full parallelizability of gates.
One of the main challenges the implementation of quantum optimization algorithms has been facing in the last year is the connectivity of qubits on quantum chips. The parity architecture has emerged as an approach to address this issue by trading qubit connectivity for an overhead in the number of physical qubits by encoding the parity of logical qubits. This qubit overhead comes with so-called parity constraints that can be implemented geometrically locally on the quantum chip. While the parity architecture is suitable for both analog and digital quantum computing, we focus on the digital side in this thesis, and present new insights on the parity approach from two perspectives. First, we investigate its resource requirements for quantum optimization, in particular for the Quantum Approximate Optimization Algorithm (QAOA), and propose a constructive algorithm to reduce these requirements compared to previous strategies. In addition, by viewing the parity constraints as stabilizers, we introduce a strategy to conserve the parity constraints throughout the execution of the QAOA. This is in contrast to previous work on the parity architecture, where the parity constraints were typically enforced via additional energy penalties. Second, we show how the parity framework can be used for universal quantum computation, and how cornerstone algorithms like the quantum Fourier transform benefit from this new approach. Our method essentially allows to trade a high circuit-depth for a qubit overhead, while at the same time offering more flexibility in circuit design by enabling on-the-fly recoding of physical qubits. Furthermore, we present a universal quantum computing approach in the parity architecture based on quantum measurements, which allows for additional reductions in circuit depth. Finally, we outline how the parity architecture can be exploited for quantum error correction. With these findings, we aim to contribute to building the bridge between the current era of non-error-corrected hardware and fault-tolerant quantum computing.
Quantum computing capabilities have developed rapidly in the last years, both in terms of experimental control of quantum systems and theoretical knowledge of quantum algorithms. During this time, the field has progressed from few-qubit prototypes to small computers that can do non-trivial calculations. In a few cases, these calculations approach the current limits of what classical computers can achieve. At this point in time, it is critical to get the maximal performance out of the available quantum hardware, which requires practical applications, smart algorithms, error mitigation and powerful decoding strategies. One near-term application of these quantum devices is quantum optimization, which utilizes quantum computers to solve combinatorial optimization problems. The way these problems are encoded on the quantum device is crucial and often requires both hardware-independent as well as hardware-specific ideas. A core part of this process is compilation, which translates the high-level quantum algorithm to instructions that can be executed on the physical quantum computer. In this thesis we focus on a specific kind of compilation, which originates from the Lechner-Hauke-Zoller model. We present the parity architecture, which is a hardware-independent way to compile arbitrary combinatorial optimization problems to quantum systems. With the parity architecture, analog and digital quantum algorithms can be executed using only local interactions, at the cost of a qubit overhead. First, we introduce a mathematical framework for the parity compiler using linear algebra and give some practical examples. This framework also allows the encoding of higher-order interactions directly, without the need to convert them to quadratic terms. We then benchmark the resource requirements of the parity architecture for digital algorithms, comparing against standard methods that use qubit routing. After that, we show how to compile for digital quantum devices with arbitrary connectivity. Here, we relax the condition that the interactions in the parity architecture are all completely local, resulting in a more flexible compilation approach. Finally, we show that parity compilation can be done constructively for any optimization problem at the cost of a qubit overhead. This qubit overhead can then be minimized by performing a search through different configurations.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
One of the potential use cases of a quantum computer is to solve combinatorial optimisation problems more efficiently than is possible with the most advanced classical computers. Combinatorial optimisation problems that appear in industry often involve a large number of constraints. This thesis investigates algorithmic techniques that improve the performance of quantum optimisation algorithms in solving problems with constraints. We test these techniques on customer data science problems. We study an alternative penalty method for encoding constraints in Ising Hamiltonians, which can be applied to various quantum algorithms. This method only introduces linear terms to the Ising Hamiltonian, allowing for more efficient use of hardware resources than the standard quadratic penalty method. These efficiency improvements are particularly beneficial for near-term devices with a limited number of qubits that are sparsely connected. We analyse the impact of using this alternative encoding method on the performance of the quantum approximate optimisation algorithm and quantum annealing applied to example problems in customer data science. Our results are based on numerical simulations and experiments on quantum hardware. We introduce a new variant of the quantum approximate optimisation algorithm that improves its ability to solve problems with constraints. In this variant of the algorithm, the strengths of penalty functions are associated with additional variational parameters, allowing them to take different values in each layer of the quantum circuit. We perform numerical simulations of multiple variants of the quantum approximate optimisation algorithm and compare their performance.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.