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:1903.10928 · Physical Review Applied

Equation Planting: A Tool for Benchmarking Ising Machines

Itay Hen

Published Jul 19, 2019• 24 citations
arXivHTMLPDF

Abstract

Recent years have witnessed the flourishing of experimental $I\phantom{\rule{0}{0ex}}s\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g$ $m\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}c\phantom{\rule{0}{0ex}}h\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}s$, special-purpose computational devices that promise to solve the world's toughest optimization problems in record times. Evaluating an Ising machine's performance is problematic, though, as it poses two seemingly contradictory requirements: On the one hand, the generated problem instances should be hard to solve, yet on the other hand they should have verifiable solutions. This study provides a methodology for generating random optimization-problem sets from linear systems of equations that possess both desired properties, thereby allowing direct, unbiased benchmarking of these physical optimization devices.

DOI
10.1103/physrevapplied.12.011003

Related papers

Benchmarking the optimization of optical machines with the planted solutions

Nikita Stroev, Natalia G. Berloff, Nir Davidson

This research focuses on developing effective benchmarks for quadratic unconstrained binary optimization instances, crucial for evaluating the performance of Ising hardware and solvers. Currently, the field lacks accessible and reproducible models for systematically testing such systems, particularly in terms of detailed phase space characterization. Here, we introduce universal generative models based on an extension of Hebb’s rule of associative memory with asymmetric pattern weights. We conduct comprehensive calculations across different scales and dynamical equations, examining outcomes like the probabilities of reaching the ground state, planted state, spurious state, or other energy levels. Additionally, the generated problems reveal properties such as the easy-hard-easy complexity transition and complex solution cluster structures. This method offers a promising platform for analyzing and understanding the behavior of physical hardware and its simulations, contributing to future advancements in optimization technologies. The authors present a method for creating generative models that produce test instances for quadratic unconstrained binary optimization (QUBO) problems, inspired by Hebb’s rule. Their approach identifies key solution patterns and complexity transitions, providing a platform to evaluate the performance of Ising hardware and solvers efficiently.

Communications Physics•Nov 19, 2024•1 citation

Ising machines as hardware solvers of combinatorial optimization problems

Naeimeh Mohseni, Peter L. McMahon, Tim Byrnes

Nature Reviews Physics•May 4, 2022•549 citations

Probing for quantum speedup in spin-glass problems with planted solutions

Itay Hen, Joshua Job, Tameem Albash +3 more

The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.

arXiv:1502.01663•Physical Review A•Oct 23, 2015•168 citations

Generating hard Ising instances with planted solutions using post-quantum cryptographic protocols

Salvatore Mandrà, Humberto Munoz-Bauza, Gianni Mossi +1 more

arXiv:2308.09704•Future Generation Computer Systems•Jan 22, 2025•7 citations

Probabilistic algorithms for Ising machines from optimization to generative AI

Corentin Delacour, Xiuqi Zhang, Abdelrahman S. Abdelrahman +4 more

arXiv:2610.03972•Nature Reviews Electrical Engineering•Oct 15, 2026•0 citations

Scalable Parallel Optical Ising Machine for Solving Large‐Scale Combinatorial Optimization Problems

Ziyao Zhang, Jie Wang, Changxin Zheng +2 more

ABSTRACT Many real‐world applications can be categorized as combinatorial optimization problems (COPs), yet their inherent NP‐hardness and exponential computational complexity pose significant barriers to efficient solutions. Designed specifically for solving COPs, the Ising machine (IM) demonstrates superior performance over traditional Von Neumann‐based computing architectures. Among different IM implementations, optical IMs (OIMs) are especially promising due to their inherent high‐speed and energy efficiency properties. Nevertheless, current OIMs are constrained by serial processing architectures, posing significant challenges for solving large‐scale COPs. To address this challenge, we propose and experimentally demonstrate a multiplexed parallel OIM architecture spanning the optical and electrical domains. The system solved a square lattice MAX‐CUT instance with over 100,000 spins and achieved a fourfold speedup with four‐channel parallelism. In addition, channel‐wise calibration mitigated device mismatch and aligned the nonlinear responses across channels, enabling the four‐channel system to maintain solution quality comparable to the single‐channel system across small benchmark problems of varying difficulty. We also explored a method combining hierarchical clustering and noise injection, which identified the known optimal route within the clustering‐constrained search space of the 14‐city TSP. These results demonstrate the potential of the proposed architecture for larger and more complex optimization problems.

Laser & Photonics Review•Oct 1, 2026•0 citations
Recent years have witnessed the flourishing of experimental I\phantom{\rule{0}{0ex}}s\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}g m\phantom{\rule{0}{0ex}}a\phantom{\rule{0}{0ex}}c\phantom{\rule{0}{0ex}}h\phantom{\rule{0}{0ex}}i\phantom{\rule{0}{0ex}}n\phantom{\rule{0}{0ex}}e\phantom{\rule{0}{0ex}}s, special-purpose computational devices that promise to solve the world's toughest optimization problems in record times. Evaluating an Ising machine's performance is problematic, though, as it poses two seemingly contradictory requirements: On the one hand, the generated problem instances should be hard to solve, yet on the other hand they should have verifiable solutions. This study provides a methodology for generating random optimization-problem sets from linear systems of equations that possess both desired properties, thereby allowing direct, unbiased benchmarking of these physical optimization devices.
This research focuses on developing effective benchmarks for quadratic unconstrained binary optimization instances, crucial for evaluating the performance of Ising hardware and solvers. Currently, the field lacks accessible and reproducible models for systematically testing such systems, particularly in terms of detailed phase space characterization. Here, we introduce universal generative models based on an extension of Hebb’s rule of associative memory with asymmetric pattern weights. We conduct comprehensive calculations across different scales and dynamical equations, examining outcomes like the probabilities of reaching the ground state, planted state, spurious state, or other energy levels. Additionally, the generated problems reveal properties such as the easy-hard-easy complexity transition and complex solution cluster structures. This method offers a promising platform for analyzing and understanding the behavior of physical hardware and its simulations, contributing to future advancements in optimization technologies. The authors present a method for creating generative models that produce test instances for quadratic unconstrained binary optimization (QUBO) problems, inspired by Hebb’s rule. Their approach identifies key solution patterns and complexity transitions, providing a platform to evaluate the performance of Ising hardware and solvers efficiently.
The availability of quantum annealing devices with hundreds of qubits has made the experimental demonstration of a quantum speedup for optimization problems a coveted, albeit elusive goal. Going beyond earlier studies of random Ising problems, here we introduce a method to construct a set of frustrated Ising-model optimization problems with tunable hardness. We study the performance of a D-Wave Two device (DW2) with up to 503 qubits on these problems and compare it to a suite of classical algorithms, including a highly optimized algorithm designed to compete directly with the DW2. The problems are generated around predetermined ground-state configurations, called planted solutions, which makes them particularly suitable for benchmarking purposes. The problem set exhibits properties familiar from constraint satisfaction (SAT) problems, such as a peak in the typical hardness of the problems, determined by a tunable clause density parameter. We bound the hardness regime where the DW2 device either does not or might exhibit a quantum speedup for our problem set. While we do not find evidence for a speedup for the hardest and most frustrated problems in our problem set, we cannot rule out that a speedup might exist for some of the easier, less frustrated problems. Our empirical findings pertain to the specific D-Wave processor and problem set we studied and leave open the possibility that future processors might exhibit a quantum speedup on the same problem set.
ABSTRACT Many real‐world applications can be categorized as combinatorial optimization problems (COPs), yet their inherent NP‐hardness and exponential computational complexity pose significant barriers to efficient solutions. Designed specifically for solving COPs, the Ising machine (IM) demonstrates superior performance over traditional Von Neumann‐based computing architectures. Among different IM implementations, optical IMs (OIMs) are especially promising due to their inherent high‐speed and energy efficiency properties. Nevertheless, current OIMs are constrained by serial processing architectures, posing significant challenges for solving large‐scale COPs. To address this challenge, we propose and experimentally demonstrate a multiplexed parallel OIM architecture spanning the optical and electrical domains. The system solved a square lattice MAX‐CUT instance with over 100,000 spins and achieved a fourfold speedup with four‐channel parallelism. In addition, channel‐wise calibration mitigated device mismatch and aligned the nonlinear responses across channels, enabling the four‐channel system to maintain solution quality comparable to the single‐channel system across small benchmark problems of varying difficulty. We also explored a method combining hierarchical clustering and noise injection, which identified the known optimal route within the clustering‐constrained search space of the 14‐city TSP. These results demonstrate the potential of the proposed architecture for larger and more complex optimization problems.