Resource-Efficient Quantum Optimization via Higher-Order Encoding

• URL: http://arxiv.org/abs/2511.17545v1
• Date: Mon, 10 Nov 2025 10:17:55 GMT
• Title: Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Authors: Frederik Koch, Shahram Panahiyan, Rick Mukherjee, Joseph Doetsch, Dieter Jaksch,
• Abstract summary: We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation.<n>Our method systematically constructs HUBO Hamiltonians and, compared to QUBO in benchmarks on Gate Assignment (GAP), k-Colorable Subgraph (MkCS), and Programming (IP) problems, exponentially reduces qubit requirements and decreases CNOT gate counts by at least 89.6%.
• Score: 0.040150524643488644
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to QUBO in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, exponentially reduces qubit requirements and decreases CNOT gate counts by at least 89.6% after compilation to single- and two-qubit gates for all tested instances. These results highlight HUBO as a practical alternative for current and near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, broadening access to resource-efficient quantum optimization.

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)
• Quantum Hardware-Efficient Selection of Auxiliary Variables for QUBO Formulations [5.74796205166378]
  We present a novel approach for the selection of auxiliary variables tailored for architectures with limited connectivity.<n>We show that, compared to circuits constructed from a QUBO formulation using conventional auxiliary selection methods, the proposed approach reduces the circuit depth by almost 40%.
  arXiv  Detail & Related papers  (2025-11-24T19:00:05Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Distributed Quantum Approximate Optimization Algorithm on a Quantum-Centric Supercomputing Architecture [1.953969470387522]
  Quantum approximate optimization algorithm (QAOA) has shown promise in solving optimization problems by providing quantum speedup on gate-based quantum computing systems.<n>However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits.<n>We present a distributed QAOA (DQAOA) which decomposes a large computational workload into smaller tasks that require fewer qubits and shallower circuits.
  arXiv  Detail & Related papers  (2024-07-29T17:42:25Z)
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations [2.9564164925541503]
  Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. We propose higher-order binary formulations that can simultaneously reduce the numbers of qubits and required gates.
  arXiv  Detail & Related papers  (2023-08-03T07:20:24Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device.<n>We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.<n>We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max-$K$-Cut and obtain circuits that are near-optimal with respect to all relevant cost measures.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59: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)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  Two-qubit gates are important components of quantum computing. But unwanted interactions between qubits (so-called parasitic gates) can degrade the performance of quantum applications. We present two software methods to mitigate parasitic two-qubit gate errors.
  arXiv  Detail & Related papers  (2021-11-08T17:37:27Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• 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)

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.