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

International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)

Targeting Classical Code to a Quantum Annealer

Scott Pakin

Published Apr 4, 2019• 7 citations
Publisher

Abstract

From a compiler's perspective, a quantum annealer represents a fundamentally different hardware target from a CPU, GPU, or other von Neumann architecture. Quantum annealers are special-purpose computers that use quantum effects to heuristically determine the set of Boolean variables that minimize a quadratic pseudo-Boolean function (an NP-hard problem). Natively programming such systems involves supplying them with a vector of function coefficients and receiving a vector of function-minimizing Booleans in return. The contribution of this work is to demonstrate how to compile conventional code into a minimization problem for solution on a quantum annealer. The resulting code can run either forward (from inputs to outputs) or backward (from outputs to inputs). We show how this capability can be exploited to simplify the expression and solution of problems in the NP complexity class.

DOI
10.1145/3297858.3304071

Related papers

C to D-Wave: A High-level C Compilation Framework for Quantum Annealers

Mohamed W. Hassan, Scott Pakin, Wu-chun Feng

A quantum annealer solves optimization problems by exploiting quantum effects. Problems are represented as Hamiltonian functions that define an energy landscape. The quantum-annealing hardware relaxes to a solution corresponding to the ground state of the energy landscape. Expressing arbitrary programming problems in terms of real-valued Hamiltonian-function coefficients is unintuitive and challenging. This paper addresses the difficulty of programming quantum annealers by presenting a compilation framework that compiles a subset of C code to a quantum machine instruction (QMI) to be executed on a quantum annealer. Our work is based on a modular software stack that facilitates programming D-Wave quantum annealers by successively lowering code from C to Verilog to a symbolic “quantum macro assembly language” and finally to a device-specific Hamiltonian function. We demonstrate the capabilities of our software stack on a set of problems written in C and executed on a D-Wave 2000Q quantum annealer.

IEEE High Performance Extreme Computing Conference•Sep 1, 2019•10 citations

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•0 citations

Quantum annealing algorithms for Boolean tensor networks

Elijah Pelofske, Georg Hahn, Daniel O’Malley +2 more

Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

arXiv:2107.13659•Scientific Reports•May 20, 2022•18 citations

Programming a D-wave annealing-based quantum computer: tools and techniques

Scott Pakin, Steven P. Reinhardt

Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.

Quantum Information and Computation•Sep 1, 2019•1 citation

Compiling Planning into Quantum Optimization Problems: A Comparative Study

Bryan O’Gorman, Eleanor Gilbert Rieffel, N. Minh +2 more

Abstract : One approach to solving planning problems is to compile them to another problem for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances encoded as Quadratic Unconstrained Binary Optimization (QUBO). Early quantum annealers are now available, and more sophisticated quantum annealers will likely be built over the next decades. Specific quantum annealing hardware implementations have specific constraints, restricting the types of QUBOs each can take as input. In this paper, we introduce the planning community to the key steps involved in compiling planning problems to quantum annealing hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we provide preliminary results from running an early quantum annealer on a parameterized family of hard planning problems. The results show that different mappings can lead to a substantial difference in performance, even when many superficial features of the resulting instances are similar. We also provide some insights gained from this early study, and suggest directions for future work.

•Jun 7, 2015•5 citations

Tucker-1 Boolean Tensor Factorization with Quantum Annealers

Daniel O’Malley, Hristo N. Djidjev, Boian S. Alexandrov

Quantum annealers are an emerging computational architecture that have the potential to address some challenging computational issues that will be left unresolved as we approach the end of the Moore's Law era of computing. D-Wave quantum annealers are designed to solve a challenging set of problems - quadratic unconstrained binary optimization problems. This makes them a natural fit for solving problems with binary or Boolean variables. Here, we explore the use of a quantum annealer to solve Boolean tensor factorization. The goal of Boolean tensor factorization is to represent a high-dimensional tensor filled with Boolean values as a product of Boolean matrices and a Boolean core tensor. We show that a particular Boolean tensor factorization problem (called Tucker-1 factorization) can be decomposed into a sequence of quadratic unconstrained binary optimization problems that can be solved with a D-Wave 2000Q quantum annealer. While quantum annealers specifically and quantum computers in general are at a fairly early stage in their development, they are currently capable of solving these Boolean tensor factorization problems. Our results show that for fairly small tensors, we are frequently able to obtain an accurate (sometimes exact) factorization using quantum annealing.

IEEE International Conference on Rebooting Computing (ICRC)•Dec 1, 2020•3 citations
From a compiler's perspective, a quantum annealer represents a fundamentally different hardware target from a CPU, GPU, or other von Neumann architecture. Quantum annealers are special-purpose computers that use quantum effects to heuristically determine the set of Boolean variables that minimize a quadratic pseudo-Boolean function (an NP-hard problem). Natively programming such systems involves supplying them with a vector of function coefficients and receiving a vector of function-minimizing Booleans in return. The contribution of this work is to demonstrate how to compile conventional code into a minimization problem for solution on a quantum annealer. The resulting code can run either forward (from inputs to outputs) or backward (from outputs to inputs). We show how this capability can be exploited to simplify the expression and solution of problems in the NP complexity class.
A quantum annealer solves optimization problems by exploiting quantum effects. Problems are represented as Hamiltonian functions that define an energy landscape. The quantum-annealing hardware relaxes to a solution corresponding to the ground state of the energy landscape. Expressing arbitrary programming problems in terms of real-valued Hamiltonian-function coefficients is unintuitive and challenging. This paper addresses the difficulty of programming quantum annealers by presenting a compilation framework that compiles a subset of C code to a quantum machine instruction (QMI) to be executed on a quantum annealer. Our work is based on a modular software stack that facilitates programming D-Wave quantum annealers by successively lowering code from C to Verilog to a symbolic “quantum macro assembly language” and finally to a device-specific Hamiltonian function. We demonstrate the capabilities of our software stack on a set of problems written in C and executed on a D-Wave 2000Q quantum annealer.
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 manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., [Formula: see text]) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor's with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.
Quantum annealing is a form of quantum computing that exploits quantum effects to probabilistically solve a specific, NP-hard problem: finding the ground state of a classical, Ising-model Hamiltonian. Because physical quantum annealers are already available, there exists the pressing question of how to program such systems. That is, how can one map a computational problem into the coefficients of an Ising-model Hamiltonian for solution by quantum-annealing hardware? In this article, we address that question primarily from a practical standpoint. We survey extant software tools intended for programming D-wave annealing-based quantum processors and examine the programming model and solution technique promoted by each tool in an attempt to showcase the variety of contemporary approaches to solving computationally challenging problems on an existing annealing-based quantum computer.
Abstract : One approach to solving planning problems is to compile them to another problem for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances encoded as Quadratic Unconstrained Binary Optimization (QUBO). Early quantum annealers are now available, and more sophisticated quantum annealers will likely be built over the next decades. Specific quantum annealing hardware implementations have specific constraints, restricting the types of QUBOs each can take as input. In this paper, we introduce the planning community to the key steps involved in compiling planning problems to quantum annealing hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we provide preliminary results from running an early quantum annealer on a parameterized family of hard planning problems. The results show that different mappings can lead to a substantial difference in performance, even when many superficial features of the resulting instances are similar. We also provide some insights gained from this early study, and suggest directions for future work.
Quantum annealers are an emerging computational architecture that have the potential to address some challenging computational issues that will be left unresolved as we approach the end of the Moore's Law era of computing. D-Wave quantum annealers are designed to solve a challenging set of problems - quadratic unconstrained binary optimization problems. This makes them a natural fit for solving problems with binary or Boolean variables. Here, we explore the use of a quantum annealer to solve Boolean tensor factorization. The goal of Boolean tensor factorization is to represent a high-dimensional tensor filled with Boolean values as a product of Boolean matrices and a Boolean core tensor. We show that a particular Boolean tensor factorization problem (called Tucker-1 factorization) can be decomposed into a sequence of quadratic unconstrained binary optimization problems that can be solved with a D-Wave 2000Q quantum annealer. While quantum annealers specifically and quantum computers in general are at a fairly early stage in their development, they are currently capable of solving these Boolean tensor factorization problems. Our results show that for fairly small tensors, we are frequently able to obtain an accurate (sometimes exact) factorization using quantum annealing.