Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables
Simon Garhofer*, Oliver Bringmann · 2024
Read Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables by Simon Garhofer*, Oliver Bringmann (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-07450.txt.
Introduction
Simon Garhofer and Oliver Bringmann shrank the qubit cost for a quantum search on the traveling salesperson puzzle, in a paper published in 2024. The standard way writes a tour as a chain of town slots, each town a one-hot code. That consumes qubits fast. Their way writes a tour by the roads it takes, then trims the spare fat.
The trim cuts the qubit count by a whole factor tied to tour size. On small tours the new code matched the accuracy grade of the old one. The cost was a slight rise in the tuning rounds the classical side needs. The authors present edge codes for the tight qubit era, where each saved qubit counts.
Catalog record
| CREATOR | Simon Garhofer*, Oliver Bringmann |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-07450
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables Thanks: This work has been supported by the Ministry of Economic Affairs Baden-Württemberg in the project SEQUOIA under project number 036-840012. Simon Garhofer*, Oliver Bringmann Abstract The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are significantly more accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly. I Introduction Combinatorial optimization problems in general and the TSP in particular are NP-hard problems, hence there are no algorithms known that return optimal solutions for this class of problems efficiently, i.e. in a feasible amount of time for growing problem instance sizes. In the worst case, algorithms that compute optimal solutions have to check every possible solution given in the problem statement, resulting in exponential runtime. In most practically relevant instances, approximation algorithms are used which compute solutions in considerably more favorable runtime at the cost of optimality [ 10 ] . Quantum computers are capable of finding optimal solutions to combinatorial optimization problems more quickly, however, the asymptotic runtime of all known algorithms is still exponential [ 8 ] [ 5 ] . Moreover, in the current era of NISQ computers algorithms of such complexity will result in extremely noisy computations, making the output effectively unusable [ 12 ] . Hence, as long as superpolynomial run-time improvements for exact quantum algorithms remain unproven, approximation algorithms are considered a viable alternative. In this work, we concern ourselves with QAOA, which for the TSP in particular offers no asymptotic runtime advantages over classical approximation algorithms [ 10 ] [ 9 ] . While there are precious few proven theoretical bounds for QAOA approximation ratios, especially for implementations using many layers, there is empirical evidence for better approximation ratios in practical applications. Further results would need to be taken from physical backends – ideally providing many more qubits than as of today [ 6 ] [ 4 ] [ 14 ] [ 2 ] . An essential aspect of any QAOA circuit is how internal states represent candidate solutions. We refer to this as the (problem) encoding. A straightforward way of constructing such an encoding is to restate a given problem as a QUBO. This QUBO is then transformed into an Ising Hamiltonian, the ground state of which is determined using QAOA [ 7 ] [ 6 ] . Dependent on the specific problem, such encodings may end up wasteful in the number of qubits. In the TSP QAOA for instance, each city is represented by a 1-hot binary string. The order of these strings depicts the sequence of cities. Our goal is to reduce the number of qubits required by leveraging phase summation effects of the tensor product for tour length computation while maintaining the expressiveness of the encoding. I-A Related work Since the TSP is a fundamental problem in classical computer science as well as ubiquitous in practical applications, it is widely covered in quantum computing research, too. State encodings in QAOA have been the subject of several works. In [ 3 ] the authors suggest replacing the 1-hot encoding with a binary encoding. Naturally, this reduces the number of required qubits from quadratic to linearithmic but leaves open a concrete circuit construction. The authors of [ 11 ] argue that simply changing the encoding to a binary representation disproportionately amplifies circuit depth, making it NISQ-unfriendly. They therefore present a hybrid encoding where the fraction of binary and 1-hot encoding can be chosen. In [ 13 ] it is suggested to divide the QUBO subspace using two qubit arrays: n_{r} register qubits are used to address 2^{n_{r}} different subsystems with n_{a} qubits. Those n_{a} qubits are then able to express arbitrarily complex correlations between classical variables. I-B Contribution We describe a more qubit-efficient QAOA circuit construction for the TSP in Section III , focusing on the problem encoding. A mathematical proof of its correctness is given. Our encoding reduces the number of required qubits by a linear factor and removes cyclic redundancies. Experimental results are shown in section IV . We find that our proposed TSP encoding helps finding good solutions considerably in small problem instances, almost doubling the rate at which optimal solutions are returned. All required preliminaries are briefly covered in section II with respective citations providing more detailed information. II Preliminaries Let G=(V,E) be a complete directed graph with vertices V,|V|=n and edges E,|E|=n^{2}-n and let c:E\rightarrow\mathbb{R} be a function that maps each edge to some cost. The TSP asks to find a tour that visits all vertices exactly once and returns to the origin vertex while the cost of the tour, determined by c , is minimal. [ 10 ] . QAOA is a hybrid algorithm for optimizing combinatorial optimization problems. The basic QAOA setup as described in [ 6 ] consists of a parametrized quantum circuit that is iteratively optimized using classical algorithms. In the quantum circuit an operator C that implements the cost function is, alternately with a mixer operator B , applied to a uniform superposition of all basis states, dependent on angles \gamma_{1},...,\gamma_{p},\beta_{1},...,\beta_{p} : \displaystyle|\gamma,\beta\rangle=e^{-i\beta_{p}B}e^{-i\gamma_{p}C}\ldots e^{-i\beta_{1}B}e^{-i\gamma_{1}C}|+\rangle The expected value \langle\gamma,\beta|C|\gamma,\beta\rangle is then minimized/maximized by some classical optimization algorithm. The procedure described in [ 9 ] extends QAOA by constructing the mixer in such a way that given problem boundary conditions are adhered to. Constraints, such as “every city has to be visited exactly once”, are therefore guaranteed to be met, whereas in standard QAOA such constraints would have to be implemented via penalty terms in C . The mixer construction is simplified in [ 1 ] , resulting in so-called Grover mixers . This modification necessitates a more complex initial state preparation, where instead of trivially preparing a single valid state (with respect to the boundary conditions), all such states are prepared in a uniform superposition. Moving circuit complexity from the mixer to the state preparation serves as a trade-off, effectively reducing circuit depth for large p given that the initial state can be prepared efficiently. Boundary conditions are enforced by only considering a proper subset of all 2^{n} states a register of n qubits can be in as a valid encoding of some TSP tour. Mixers in the Alternating Operator Ansatz and thus