Quantum Annealing-Based Software Components: An Experimental Case Study with SAT Solving

Abstract

Quantum computers have the potential of solving problems more efficiently than classical computers. While first commercial prototypes have become available, the performance of such machines in practical application is still subject to exploration. Quantum computers will not entirely replace classical machines, but serve as accelerators for specific problems. This necessitates integrating quantum computational primitives into existing applications. In this paper, we perform a case study on how to augment existing software with quantum computational primitives for the Boolean satisfiability problem (SAT) implemented using a quantum annealer (QA). We discuss relevant quality measures for quantum components, and show that mathematically equivalent, but structurally different ways of transforming SAT to a QA can lead to substantial differences regarding these qualities. We argue that engineers need to be aware that (and which) details, although they may be less relevant in traditional software engineering, require considerable attention in quantum computing.

References in corpus (11)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Ising formulations of many NP problems
• Elucidating Reaction Mechanisms on Quantum Computers
• ProjectQ: An Open Source Software Framework for Quantum Computing
• Quantum Algorithms for Fermionic Simulations
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Q#: Enabling scalable quantum computing and development with a high-level domain-specific language
• A Software Methodology for Compiling Quantum Programs
• Flight Gate Assignment with a Quantum Annealer
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing

Cited by in corpus (7)

• Polynomial Reduction Methods and their Impact on QAOA Circuits
• Approximating under the Influence of Quantum Noise and Compute Power
• Guided-SPSA: Simultaneous Perturbation Stochastic Approximation assisted by the Parameter Shift Rule
• Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains