A Comparison of Quadratic and Higher-Order Representations for QAOA

• URL: http://arxiv.org/abs/2509.20127v1
• Date: Wed, 24 Sep 2025 13:53:50 GMT
• Title: A Comparison of Quadratic and Higher-Order Representations for QAOA
• Abstract summary: We consider a routing problem and compare quadratic and higher-order representations using the Quantum Approximate optimisation algorithm (QAOA)<n>We find that the higher-order form yields better solution quality and scales better in terms of numbers of qubits, but requires more two-qubit gates.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work we consider a routing problem and compare quadratic and higher-order representations using the Quantum Approximate Optimisation Algorithm (QAOA). The majority of works investigating QAOA use quadratic Hamiltonians to represent the considered problems, which can lead to poor scaling in qubit requirements. We address the gap of direct comparisons between quadratic and higher-order forms through an investigation into two distinct formulations of the same use case. We find that the higher-order form yields better solution quality and scales better in terms of numbers of qubits, but requires more two-qubit gates. We additionally consider a factoring method to reduce the gate depth of the higher-order version, which achieves a significant reduction in the number of two-qubit gates when run on real IBM hardware.

Related papers

• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  We study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces.<n>We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions.<n>Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum optimization.
  arXiv  Detail & Related papers  (2026-02-07T04:37:32Z)
• PCDVQ: Enhancing Vector Quantization for Large Language Models via Polar Coordinate Decoupling [53.91873442457923]
  Vector Quantization (VQ) serves as a prevalent solution to this issue for its extremely low-bit (even at 2-bit) and considerable accuracy.<n>This paper proposes Polar Coordinate Decoupled Vector Quantization (PCDVQ), an effective and efficient VQ framework.<n> Experimental results show that PCDVQ outperforms baseline methods at 2-bit level by at least 1.5% zero-shot accuracy.
  arXiv  Detail & Related papers  (2025-06-05T08:58:58Z)
• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  We show a more qubit-efficient circuit construction for optimization problems by the example of the Travelingperson Sales Problem (TSP)<n>Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding.<n>Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical iterations increases only slightly.
  arXiv  Detail & Related papers  (2024-12-10T12:12:34Z)
• Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
  We show that the search space of the quadratic assignment problem can be reduced using Grover adaptive search (GAS) with Dicke state operators. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty.
  arXiv  Detail & Related papers  (2024-10-16T03:00:37Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• QAOA of the Highest Order [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) has been one of the leading candidates for near-term quantum advantage in gate-model quantum computers. This paper gives an example of a graph coloring problem that, depending on its variable encoding scheme, optionally admits higher order terms. The evidence then motivates an analysis of the scaling behavior of QAOA in this higher order formulation for an ensemble of graph coloring problems.
  arXiv  Detail & Related papers  (2021-11-24T19:29:44Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• A polynomial size model with implicit SWAP gate counting for exact qubit reordering [0.0]
  Quantum circuit designers must adhere to the constraints posed by the limited interaction distance of qubits. We consider the Nearest Neighbor Compliance problem on a linear array, where the number of required SWAP gates is to be minimized.
  arXiv  Detail & Related papers  (2020-09-18T11:06:19Z)

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.