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:2111.12063

Quantum Advantage for All

Christoph M. Kirsch, Stefanie Muroya

Published Nov 23, 2021• 0 citations
arXivHTMLPDF

Abstract

We show that the algorithmic complexity of any classical algorithm written in a Turing-complete programming language polynomially bounds the number of quantum bits that are required to run and even symbolically execute the algorithm on a quantum computer. In particular, we show that any classical algorithm $A$ that runs in $\mathcal{O}(f(n))$ time and $\mathcal{O}(g(n))$ space requires no more than $\mathcal{O}(f(n)\cdot g(n))$ quantum bits to execute, even symbolically, on a quantum computer. With $\mathcal{O}(1)\leq\mathcal{O}(g(n))\leq\mathcal{O}(f(n))$ for all $n$, the quantum bits required to execute $A$ may therefore not exceed $\mathcal{O}(f(n)^2)$ and may come down to $\mathcal{O}(f(n))$ if memory consumption by $A$ is bounded by a constant. Our construction works by encoding symbolic execution of machine code in a finite state machine over the satisfiability-modulo-theory (SMT) of bitvectors, for modeling CPU registers, and arrays of bitvectors, for modeling main memory. The FSM is linear in the size of the code, independent of execution time and space, and represents the reachable machine states for any given input. The FSM may be explored by bounded model checkers using SMT and SAT solvers as backend. However, for the purpose of this paper, we focus on quantum computing by unrolling and bit-blasting the FSM into (1)~satisfiability-preserving quadratic unconstrained binary optimization (QUBO) models targeting adiabatic forms of quantum computing such as quantum annealing, and (2)~semantics-preserving quantum circuits (QCs) targeting gate-model quantum computers. With our compact QUBOs, real quantum annealers can now execute simple but real code even symbolically, yet only with potential but no guarantee for exponential speedup, and with our QCs as oracles, Grover's algorithm applies to symbolic execution of arbitrary code, guaranteeing at least in theory a quadratic speedup.

DOI
10.48550/arxiv.2111.12063

Related papers

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024

arXiv:2303.11317•Physical Review X•Nov 1, 2024•27 citations

Quantum-Based SMT Solving for String Theory

Beatrice Casey, Joanna C. S. Santos, Andrew Hennessee

Satisfiability Modulo Theory (SMT) solvers are a useful tool that can be applied to a variety of problems, such as configuring relationships in distributed systems, detecting race conditions, and program analysis. String constraints are particularly difficult for SMT solvers to navigate, as the search space is generally large. Often times, classical SMT solvers will have to quit generating a solution for string constraints because it takes too long to find the solution. Quantum computing offers the advantages of quantum mechanics (e.g., superposition), which allows a system to explore a large search space much more efficiently. In this work, we explore creating a quantum-enabled SMT solver for string theory by using quantum annealing and Quadratic Unconstrained Binary Optimization (QUBO). Our preliminary results demonstrate that it is feasible to transform these string constraints to QUBO, and generate solutions for given constraints.

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)•Jul 20, 2025•0 citations

Quantum advantage

Steven Herbert

Abstract There is one question that, more than any other, pervades quantum computing: Is there a quantum advantage? This question may be asked either in general – of quantum mechanics as a model of computation – or for specified individual algorithms. In both cases, to even pose this question in a rigorous and meaningful way, a number of non-trivial prerequisites are required. These prerequisites mainly belong in the domain of computational complexity theory. This chapter defines the relevant classical and quantum computational complexity classes and includes classes of quantum circuits, such as instantaneous quantum polynomial (IQP) circuits, that provide compelling evidence that quantum mechanics indeed offers an exponential computational advantage. Also included are classes of circuits that are known not to enjoy a quantum advantage, most notably stabiliser circuits, that are extremely non-classical from a physics perspective, but can nevertheless be efficiently simulated on a classical computer, as proven in the famous Gottesman–Knill theorem.

•Dec 8, 2025•0 citations

Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms

Tuhin Sahai, Anurag Mishra, José Miguel Pasini +1 more

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.

arXiv:1910.13088•Proceedings of the AAAI Conference on Artificial Intelligence•Apr 3, 2020•2 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,500 citations

Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms

Tuhin Sahai, Anurag Mishra, José Miguel Pasini +1 more

Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.

•Apr 3, 2020•4 citations
We show that the algorithmic complexity of any classical algorithm written in a Turing-complete programming language polynomially bounds the number of quantum bits that are required to run and even symbolically execute the algorithm on a quantum computer. In particular, we show that any classical algorithm AAA that runs in O(f(n))\mathcal{O}(f(n))O(f(n)) time and O(g(n))\mathcal{O}(g(n))O(g(n)) space requires no more than O(f(n)⋅g(n))\mathcal{O}(f(n)\cdot g(n))O(f(n)⋅g(n)) quantum bits to execute, even symbolically, on a quantum computer. With O(1)≤O(g(n))≤O(f(n))\mathcal{O}(1)\leq\mathcal{O}(g(n))\leq\mathcal{O}(f(n))O(1)≤O(g(n))≤O(f(n)) for all nnn, the quantum bits required to execute AAA may therefore not exceed O(f(n)2)\mathcal{O}(f(n)^2)O(f(n)2) and may come down to O(f(n))\mathcal{O}(f(n))O(f(n)) if memory consumption by AAA is bounded by a constant. Our construction works by encoding symbolic execution of machine code in a finite state machine over the satisfiability-modulo-theory (SMT) of bitvectors, for modeling CPU registers, and arrays of bitvectors, for modeling main memory. The FSM is linear in the size of the code, independent of execution time and space, and represents the reachable machine states for any given input. The FSM may be explored by bounded model checkers using SMT and SAT solvers as backend. However, for the purpose of this paper, we focus on quantum computing by unrolling and bit-blasting the FSM into (1)~satisfiability-preserving quadratic unconstrained binary optimization (QUBO) models targeting adiabatic forms of quantum computing such as quantum annealing, and (2)~semantics-preserving quantum circuits (QCs) targeting gate-model quantum computers. With our compact QUBOs, real quantum annealers can now execute simple but real code even symbolically, yet only with potential but no guarantee for exponential speedup, and with our QCs as oracles, Grover's algorithm applies to symbolic execution of arbitrary code, guaranteeing at least in theory a quadratic speedup.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
Satisfiability Modulo Theory (SMT) solvers are a useful tool that can be applied to a variety of problems, such as configuring relationships in distributed systems, detecting race conditions, and program analysis. String constraints are particularly difficult for SMT solvers to navigate, as the search space is generally large. Often times, classical SMT solvers will have to quit generating a solution for string constraints because it takes too long to find the solution. Quantum computing offers the advantages of quantum mechanics (e.g., superposition), which allows a system to explore a large search space much more efficiently. In this work, we explore creating a quantum-enabled SMT solver for string theory by using quantum annealing and Quadratic Unconstrained Binary Optimization (QUBO). Our preliminary results demonstrate that it is feasible to transform these string constraints to QUBO, and generate solutions for given constraints.
Abstract There is one question that, more than any other, pervades quantum computing: Is there a quantum advantage? This question may be asked either in general – of quantum mechanics as a model of computation – or for specified individual algorithms. In both cases, to even pose this question in a rigorous and meaningful way, a number of non-trivial prerequisites are required. These prerequisites mainly belong in the domain of computational complexity theory. This chapter defines the relevant classical and quantum computational complexity classes and includes classes of quantum circuits, such as instantaneous quantum polynomial (IQP) circuits, that provide compelling evidence that quantum mechanics indeed offers an exponential computational advantage. Also included are classes of circuits that are known not to enjoy a quantum advantage, most notably stabiliser circuits, that are extremely non-classical from a physics perspective, but can nevertheless be efficiently simulated on a classical computer, as proven in the famous Gottesman–Knill theorem.
Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.