Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables

• URL: http://arxiv.org/abs/2412.07450v1
• Date: Tue, 10 Dec 2024 12:12:34 GMT
• Title: Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables
• Authors: Simon Garhofer, Oliver Bringmann,
• Abstract summary: We show a more qubit-efficient circuit construction for optimization problems by the example of the Travelingperson Sales Problem (TSP) Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. Our experiments show that for small instances results are significantly more accurate using our proposed encoding.
• Score: 0.7015624626359264
• License:
• 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.

Related papers

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  We propose an elaborate combination of two decomposition methods, namely graph shrinking and circuit cutting. Our results offer insights into the performance of algorithms for optimization problems within the constraints of current quantum technology.
  arXiv  Detail & Related papers  (2024-04-08T14:19:25Z)
• Indirect Quantum Approximate Optimization Algorithms: application to the TSP [1.1786249372283566]
  Quantum Alternating Operator Ansatz takes into consideration a general parameterized family of unitary operators to efficiently model the Hamiltonian describing the set of vectors. This algorithm creates an efficient alternative to QAOA, where: 1) a Quantum parametrized circuit executed on a quantum machine models the set of string vectors; 2) a Classical meta-optimization loop executed on a classical machine; 3) an estimation of the average cost of each string vector computing.
  arXiv  Detail & Related papers  (2023-11-06T17:39:14Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
  We numerically simulate solving MaxCut problems using QAOA with cat qubits. We show that running QAOA with cat qubits increases the approximation ratio for random instances of MaxCut with respect to qubits encoded into two-level systems.
  arXiv  Detail & Related papers  (2023-05-09T15:44:52Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem [2.840363325289377]
  We propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO) We conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by Grover adaptive search (GAS) Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation.
  arXiv  Detail & Related papers  (2022-08-10T06:59:43Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Optimal qubit assignment and routing via integer programming [0.22940141855172028]
  We consider the problem of mapping a logical quantum circuit onto a given hardware with limited two-qubit connectivity. We model this problem as an integer linear program, using a network flow formulation with binary variables. We consider several cost functions: an approximation of the fidelity of the circuit, its total depth, and a measure of cross-talk.
  arXiv  Detail & Related papers  (2021-06-11T15:02:26Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.