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

Digitale Welt

Towards Understanding Approximation Complexity on a Quantum Annealer

Irmi Sax, Sebastian Feld, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff–Popien, Wolfgang Mauerer

Published Dec 4, 2019• 1 citation
Publisher
DOI
10.1007/s42354-019-0244-1

Related papers

Approximate Approximation on a Quantum Annealer

Irmi Sax, Sebastian Feld, Sebastian Zielinski +3 more

Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems. While first implementations of QA have become commercially available, their practical benefits are far from fully explored. To the best of our knowledge, approximation techniques have not yet received substantial attention. In this paper, we explore how problems' approximate versions of varying degree can be systematically constructed for quantum annealer programs, and how this influences result quality or the handling of larger problem instances on given set of qubits. We illustrate various approximation techniques on both, simulations and real QA hardware, on different seminal problems, and interpret the results to contribute towards a better understanding of the real-world power and limitations of current-state and future quantum computing.

arXiv:2004.09267•Jan 1, 2020•4 citations

Applications on quantum annealers

Dennis Willsch

•Jan 1, 2026•0 citations

Nonstoquastic Hamiltonians and quantum annealing of an Ising spin glass

Layla Hormozi, Ethan Brown, Giuseppe Carleo +1 more

Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.

arXiv:1609.06558•Physical review. B./Physical review. B•May 15, 2017•109 citations

Progress Towards Quantum Annealer v2.0 II: Theory

Dvir Kafri, Chris Quintana, Yu Chen +2 more

Bulletin of the American Physical Society•Mar 5, 2018•0 citations

Role of Classical Hardness for Quantum Annealers

Itay Hen, Víctor Martín-Mayor

Bulletin of the American Physical Society•Mar 4, 2015•0 citations

Extending Quantum-Annealing-Aided Multi-User Detection to QAM Signals

Kouki Yonaga, Soma Hayabe, Kenichi Takizawa

This study presents a quantum-annealing-aided multi-user detection (QA-aided MUD) framework for quadrature amplitude modulation (QAM) signals and evaluates its performance. The proposed approach approximates log-likelihood ratios (LLRs) using quantum annealing, enabling accurate detection without exhaustive computation. Previous studies have primarily focused on quadrature phase shift keying (QPSK) modulation and have shown that QA-aided MUD can outperform conventional low-complexity detectors, particularly in overloaded multi-user multi-input multi-output (MU-MIMO) systems in uplink. In this study, we extend the QA-aided MUD framework to support QAM modulation by constructing a binary-variable formulation and incorporating a bit-level conversion scheme to handle Gray-coded constellations. For performance evaluation, block error rate (BLER) analysis is conducted using a digital annealing, while small-scale bit error rate (BER) analysis is performed using the D-Wave quantum annealer. The results demonstrate competitive, and often superior, BLER performance compared with conventional low-complexity detectors, particularly in overloaded scenarios. However, the detection performance becomes increasingly sensitive to annealing parameters as the modulation order increases. Furthermore, BER analysis indicates that the current D-Wave hardware may fail to reliably detect QAM symbols in some large problem instances. Based on these findings, future challenges for QA-aided MUD are discussed.

IEEE International Mediterranean Conference on Communications and Networking (MeditCom)•Jul 1, 2026•0 citations
Many problems of industrial interest are NP-complete, and quickly exhaust resources of computational devices with increasing input sizes. Quantum annealers (QA) are physical devices that aim at this class of problems by exploiting quantum mechanical properties of nature. However, they compete with efficient heuristics and probabilistic or randomised algorithms on classical machines that allow for finding approximate solutions to large NP-complete problems. While first implementations of QA have become commercially available, their practical benefits are far from fully explored. To the best of our knowledge, approximation techniques have not yet received substantial attention. In this paper, we explore how problems' approximate versions of varying degree can be systematically constructed for quantum annealer programs, and how this influences result quality or the handling of larger problem instances on given set of qubits. We illustrate various approximation techniques on both, simulations and real QA hardware, on different seminal problems, and interpret the results to contribute towards a better understanding of the real-world power and limitations of current-state and future quantum computing.
Quantum annealers are computing machines that utilize quantum effects to solve hard optimization problems. Understanding the circumstances under which quantum annealers are more efficient than other optimization methods is a challenging open problem. A clue to this conundrum comes from studying the complexity of quantum annealers. In general, the complexity of a physical system relates to how efficiently the system can be simulated by classical algorithms. One then asks: if some class of quantum annealers are hard to simulate classically, are they also more powerful optimization machines? Here, the authors study quantum annealers belonging to two different complexity classes: the so-called ``stoquastic'' systems, which can be efficiently simulated with classical algorithms, and ``nonstoquastic'' systems, currently with no efficient classical treatment. Applied to a prototypical optimization problem, the authors observe that, on average, the stoquastic systems perform better on easier instances of the problem, while the more complex nonstoquastic annealers show significant advantage when applied to the hardest instances. The authors conjecture that the performance of the nonstoquastic Hamiltonians is closely related to their internal structure during the annealing process and elucidate how properties such as magnetic frustration can play a key role in devising more powerful quantum annealers.
This study presents a quantum-annealing-aided multi-user detection (QA-aided MUD) framework for quadrature amplitude modulation (QAM) signals and evaluates its performance. The proposed approach approximates log-likelihood ratios (LLRs) using quantum annealing, enabling accurate detection without exhaustive computation. Previous studies have primarily focused on quadrature phase shift keying (QPSK) modulation and have shown that QA-aided MUD can outperform conventional low-complexity detectors, particularly in overloaded multi-user multi-input multi-output (MU-MIMO) systems in uplink. In this study, we extend the QA-aided MUD framework to support QAM modulation by constructing a binary-variable formulation and incorporating a bit-level conversion scheme to handle Gray-coded constellations. For performance evaluation, block error rate (BLER) analysis is conducted using a digital annealing, while small-scale bit error rate (BER) analysis is performed using the D-Wave quantum annealer. The results demonstrate competitive, and often superior, BLER performance compared with conventional low-complexity detectors, particularly in overloaded scenarios. However, the detection performance becomes increasingly sensitive to annealing parameters as the modulation order increases. Furthermore, BER analysis indicates that the current D-Wave hardware may fail to reliably detect QAM symbols in some large problem instances. Based on these findings, future challenges for QA-aided MUD are discussed.