Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.07163

Exact Spin Elimination for Quadratic and k-Local Ising Optimization

Natalia G. Berloff

Published May 12, 2025• 3 citations
arXivHTMLPDF

Abstract

Ising solvers have a finite spin budget. Quadratization uses auxiliary spins to replace higher-order interactions by pairwise ones. We show that removing spins while allowing more complex interactions can fit larger problems within the same spin budget and improve optimization. Walsh elimination minimizes over one spin at a time, writes the resulting interaction as a sum of spin products in the Walsh basis, and stores a rule for recovering the removed spin. Explicit resource limits control which eliminations are accepted. In a held-out test with the protocol frozen before instance generation and one annealing schedule shared by both formulations, mean observed success rises from 10.4% to 97.5% on sparse quadratic spin glasses and from 16.9% to 87.5% on three-body problems. Observed success increases on every instance with a verified reference minimum, and pooled time-to-solution estimates decrease by factors of about 34 and 11, respectively, with preprocessing included. For zero-field pairwise models on connected simple cubic graphs with more than four vertices, we prove that a fixed spin budget accommodates 50% larger inputs while retaining pairwise interactions, zero fields, residual degree at most six, and no increase in coupling count. These results establish exact spin elimination as a controlled trade between active-spin capacity and interaction complexity.

DOI
10.48550/arxiv.2505.07163

Related papers

An iterative Ising decoder for quantum error correction codes

Yuanqi Liu, Weilei Zeng, Peixiang Li +6 more

The Ising framework maps the decoding problem in quantum error correction onto ground-state optimization of a classical Hamiltonian, in which $X$-$Z$ error correlations enter as cross terms. Under phenomenological depolarizing noise, the exact joint formulation contains up to 8-body interactions for the toric code and 10-body for the $6.6.6$ color code. These high-order terms degrade solver convergence, inflate runtime, and raise the auxiliary spin overhead when embedding into native 2-body Ising hardware. In this work, we propose the iterative low-order decoding (ILOD) algorithm, which alternates between $X$- and $Z$-type sub-Hamiltonians, approximating cross-type correlations through Bayesian priors that reweight each type's couplings using the other type's inferred error configuration. This halves the maximum body count of interaction terms in the Hamiltonian, accelerating the solver, restoring convergence at larger code distances, and reducing the total spin count for 2-body embedding by a factor of $2.5$. For the toric code, ILOD attains a threshold of $4.73%$ versus $4.83%$ for the joint formulation, with the empirical runtime ratio scaling as $(0.81)^d$. For the $6.6.6$ color code, their thresholds agree within statistical uncertainty for small code distances, and ILOD remains convergent for larger distances where the joint formulation fails to converge despite a larger annealing budget.

quant-pharXiv:2606.12301•Quantum Science and Technology•Jun 11, 2026•1 citation

Compressed Quadratization of Higher Order Binary Optimization Problems

Avradip Mandal, Arnab Roy, Sarvagya Upadhyay +1 more

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

arXiv:2001.00658•DCC•Mar 1, 2020•45 citations

A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

Chengsi Mao, Pavel Mosharev, Yao Wang +1 more

The Ising model is ubiquitous in various optimization problems but notoriously difficult to solve due to combinatorial explosion. In view of this, Hamiltonian reduction is a useful preprocessing technique for reducing the effective problem size before applying heuristic solvers. However, existing reduction techniques mainly target second-order Ising models, whereas many pseudo-Boolean formulations naturally contain higher-order interactions. In this work, we generalize the concept of non-separable groups to arbitrary-order Ising-like models and develop a Hamiltonian reduction framework that iteratively detects and merges constrained spin groups into single variables. We benchmark the reduction on synthetic hypergraphs and higher-order network datasets, and evaluate its integration with downstream order-reduction and solver workflows. Our results establish a foundation for Hamiltonian reduction in higher-order Ising-like optimization problems.

quant-pharXiv:2607.19871•Quantum Information Processing•Jul 23, 2026•0 citations

Quantum Control without Quantum States

Modesto Orozco-Ruiz, Nguyen H. Le, Florian Mintert

We show that combining ideas from the fields of quantum invariants and optimal control can be used to design optimal quantum control solutions without explicit reference to quantum states. The states are specified only implicitly in terms of operators to which they are eigenstates. The scaling in numerical effort of the resultant approach is not given by the typically exponentially growing effort required for the specification of a time-evolved quantum state, but it is given by the effort required for the specification of a time-evolved operator. For certain Hamiltonians, this effort can be polynomial in the system size. We describe how control problems for state preparation and the realization of propagators can be formulated in this approach, and we provide explicit control solutions for a spin chain with an extended Ising Hamiltonian. The states considered for state-preparation protocols include eigenstates of Hamiltonians with more than pairwise interactions and these Hamiltonians are also used for the definition of target propagators. The cost of describing suitable time-evolving operators grows only quadratically with the system size, allowing us to construct explicit control solutions for up to 50 spins. While subexponential scaling is obtained only in special cases, we provide several examples that demonstrate favorable scaling beyond the extended Ising model. Published by the American Physical Society 2024

arXiv:2405.15609•PRX Quantum•Dec 20, 2024•5 citations

Exact Mixed-Locality Encodings for Resource-Constrained QAOA

Jingcong Liu, Yiding Su, Ruojun Zhang +3 more

Higher-order objectives possess many exact Hamiltonian encodings, and these encodings differ in the qubits, penalties, gates, and depth that they require. Representation selection is therefore an algorithmic decision for the quantum approximate optimisation algorithm on resource-constrained hardware. This work develops a pointwise-exact family of representations in which selected higher-order interactions are replaced by shared Rosenberg auxiliaries while the remaining interactions stay native. A sharp single-step penalty condition and a closed form for cubic residuals certify exactness at every stage of such a selective reduction. Within the direct-pair class, a static feasibility theory identifies infinite families of objectives for which a mixed representation meets joint budgets that exclude both the native and the fully reduced endpoint. A separate construction extends this separation to gate and depth limits under a fixed synthesis. Compilation on 12-qubit line, ring, and grid targets finds certified mixed-only regions for 23 of 30 weighted maximum three-satisfiability instances, all 30 constructed instances, and 2 of 30 cubic spin-glass instances under the stated class and penalty rule. A separate routing experiment retains 52.9% of mixed-only budget points across five seeds within fixed candidate sets. In noiseless depth-one evaluation, the native encoding attains the best mean objective under the tested protocols, and the joint resource-and-quality test finds no mixed-only success at the primary budget. Resource feasibility is thus a sound reason to select a mixed encoding, whereas solution quality requires a separate assessment.

arXiv:2611.15663•Nov 11, 2026•0 citations

Analysis of the relation between quadratic unconstrained binary optimization and the spin-glass ground-state problem

Stefan Boettcher

An inherent weakness in a widely used formulation of the Quadratic Unconstrained Binary Optimization problem is revealed when transformed into an Ising spin glass. In the ground state, spins in the glass experience external magnetic fields, many of which are of a sizable magnitude to entirely coerce their spins into alignment, irrespective of any coupling; only a small fraction of spins can resist. Thus, the effective size of this NP-hard combinatorial problem is much smaller than is apparent from the number of variables involved.

arXiv:1906.10036•Physical Review Research•Dec 3, 2019•19 citations
Ising solvers have a finite spin budget. Quadratization uses auxiliary spins to replace higher-order interactions by pairwise ones. We show that removing spins while allowing more complex interactions can fit larger problems within the same spin budget and improve optimization. Walsh elimination minimizes over one spin at a time, writes the resulting interaction as a sum of spin products in the Walsh basis, and stores a rule for recovering the removed spin. Explicit resource limits control which eliminations are accepted. In a held-out test with the protocol frozen before instance generation and one annealing schedule shared by both formulations, mean observed success rises from 10.4% to 97.5% on sparse quadratic spin glasses and from 16.9% to 87.5% on three-body problems. Observed success increases on every instance with a verified reference minimum, and pooled time-to-solution estimates decrease by factors of about 34 and 11, respectively, with preprocessing included. For zero-field pairwise models on connected simple cubic graphs with more than four vertices, we prove that a fixed spin budget accommodates 50% larger inputs while retaining pairwise interactions, zero fields, residual degree at most six, and no increase in coupling count. These results establish exact spin elimination as a controlled trade between active-spin capacity and interaction complexity.
The Ising framework maps the decoding problem in quantum error correction onto ground-state optimization of a classical Hamiltonian, in which XXX-ZZZ error correlations enter as cross terms. Under phenomenological depolarizing noise, the exact joint formulation contains up to 8-body interactions for the toric code and 10-body for the 6.6.66.6.66.6.6 color code. These high-order terms degrade solver convergence, inflate runtime, and raise the auxiliary spin overhead when embedding into native 2-body Ising hardware. In this work, we propose the iterative low-order decoding (ILOD) algorithm, which alternates between XXX- and ZZZ-type sub-Hamiltonians, approximating cross-type correlations through Bayesian priors that reweight each type's couplings using the other type's inferred error configuration. This halves the maximum body count of interaction terms in the Hamiltonian, accelerating the solver, restoring convergence at larger code distances, and reducing the total spin count for 2-body embedding by a factor of 2.52.52.5. For the toric code, ILOD attains a threshold of 4.734.73%4.73 versus 4.834.83%4.83 for the joint formulation, with the empirical runtime ratio scaling as (0.81)d(0.81)^d(0.81)d. For the 6.6.66.6.66.6.6 color code, their thresholds agree within statistical uncertainty for small code distances, and ILOD remains convergent for larger distances where the joint formulation fails to converge despite a larger annealing budget.
Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.
The Ising model is ubiquitous in various optimization problems but notoriously difficult to solve due to combinatorial explosion. In view of this, Hamiltonian reduction is a useful preprocessing technique for reducing the effective problem size before applying heuristic solvers. However, existing reduction techniques mainly target second-order Ising models, whereas many pseudo-Boolean formulations naturally contain higher-order interactions. In this work, we generalize the concept of non-separable groups to arbitrary-order Ising-like models and develop a Hamiltonian reduction framework that iteratively detects and merges constrained spin groups into single variables. We benchmark the reduction on synthetic hypergraphs and higher-order network datasets, and evaluate its integration with downstream order-reduction and solver workflows. Our results establish a foundation for Hamiltonian reduction in higher-order Ising-like optimization problems.
We show that combining ideas from the fields of quantum invariants and optimal control can be used to design optimal quantum control solutions without explicit reference to quantum states. The states are specified only implicitly in terms of operators to which they are eigenstates. The scaling in numerical effort of the resultant approach is not given by the typically exponentially growing effort required for the specification of a time-evolved quantum state, but it is given by the effort required for the specification of a time-evolved operator. For certain Hamiltonians, this effort can be polynomial in the system size. We describe how control problems for state preparation and the realization of propagators can be formulated in this approach, and we provide explicit control solutions for a spin chain with an extended Ising Hamiltonian. The states considered for state-preparation protocols include eigenstates of Hamiltonians with more than pairwise interactions and these Hamiltonians are also used for the definition of target propagators. The cost of describing suitable time-evolving operators grows only quadratically with the system size, allowing us to construct explicit control solutions for up to 50 spins. While subexponential scaling is obtained only in special cases, we provide several examples that demonstrate favorable scaling beyond the extended Ising model. Published by the American Physical Society 2024
Higher-order objectives possess many exact Hamiltonian encodings, and these encodings differ in the qubits, penalties, gates, and depth that they require. Representation selection is therefore an algorithmic decision for the quantum approximate optimisation algorithm on resource-constrained hardware. This work develops a pointwise-exact family of representations in which selected higher-order interactions are replaced by shared Rosenberg auxiliaries while the remaining interactions stay native. A sharp single-step penalty condition and a closed form for cubic residuals certify exactness at every stage of such a selective reduction. Within the direct-pair class, a static feasibility theory identifies infinite families of objectives for which a mixed representation meets joint budgets that exclude both the native and the fully reduced endpoint. A separate construction extends this separation to gate and depth limits under a fixed synthesis. Compilation on 12-qubit line, ring, and grid targets finds certified mixed-only regions for 23 of 30 weighted maximum three-satisfiability instances, all 30 constructed instances, and 2 of 30 cubic spin-glass instances under the stated class and penalty rule. A separate routing experiment retains 52.9% of mixed-only budget points across five seeds within fixed candidate sets. In noiseless depth-one evaluation, the native encoding attains the best mean objective under the tested protocols, and the joint resource-and-quality test finds no mixed-only success at the primary budget. Resource feasibility is thus a sound reason to select a mixed encoding, whereas solution quality requires a separate assessment.
An inherent weakness in a widely used formulation of the Quadratic Unconstrained Binary Optimization problem is revealed when transformed into an Ising spin glass. In the ground state, spins in the glass experience external magnetic fields, many of which are of a sizable magnitude to entirely coerce their spins into alignment, irrespective of any coupling; only a small fraction of spins can resist. Thus, the effective size of this NP-hard combinatorial problem is much smaller than is apparent from the number of variables involved.