A Quantum SMT Solver for Bit-Vector Theory
- URL: http://arxiv.org/abs/2303.09353v1
- Date: Thu, 16 Mar 2023 14:32:50 GMT
- Title: A Quantum SMT Solver for Bit-Vector Theory
- Authors: Shang-Wei Lin, Si-Han Chen, Tzu-Fan Wang and Yean-Ru Chen
- Abstract summary: We develop a quantum SMT solver for the bit-vector theory.
With the characteristic of superposition in quantum system, our solver is able to consider all the inputs simultaneously.
- Score: 2.1401240672387574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a formula $F$ of satisfiability modulo theory (SMT), the classical SMT
solver tries to (1) abstract $F$ as a Boolean formula $F_B$, (2) find a Boolean
solution to $F_B$, and (3) check whether the Boolean solution is consistent
with the theory. Steps~{(2)} and (3) may need to be performed back and forth
until a consistent solution is found. In this work, we develop a quantum SMT
solver for the bit-vector theory. With the characteristic of superposition in
quantum system, our solver is able to consider all the inputs simultaneously
and check their consistency between Boolean and the theory domains in one shot.
Related papers
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Light Schrödinger Bridge [72.88707358656869]
We develop a lightweight, simulation-free and theoretically justified Schr"odinger Bridges solver.
Our light solver resembles the Gaussian mixture model which is widely used for density estimation.
Inspired by this similarity, we also prove an important theoretical result showing that our light solver is a universal approximator of SBs.
arXiv Detail & Related papers (2023-10-02T13:06:45Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game.
We also show that no one can benefit unilaterally from the general theory step by step.
arXiv Detail & Related papers (2023-01-19T11:36:50Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
Faults are by nature while most man-made systems, and especially computers, work deterministically.
This paper provides such a connecting via quantum information theory which is an intuitive approach as quantum physics obeys probability laws.
arXiv Detail & Related papers (2022-09-08T17:55:30Z) - Exact quantum query complexity of computing Hamming weight modulo powers
of two and three [2.1349209400003932]
We show that the exact quantum query complexity of this problem is $leftlceil n (1 - 1/m) rightil$.
The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm.
arXiv Detail & Related papers (2021-12-29T17:57:41Z) - Preparing exact eigenstates of the open XXZ chain on a quantum computer [0.0]
We formulate a quantum algorithm for preparing Bethe states of this model, corresponding to real solutions of the Bethe equations.
The algorithm is probabilistic, with a success probability that decreases with the number of down spins.
arXiv Detail & Related papers (2021-09-12T20:29:43Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry.
We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z) - Quantum logics close to Boolean algebras [0.0]
We consider orthomodular posets endowed with a symmetric difference.
We consider quantum logics with an XOR-type connective.
Let us only note that the orthomodular posets pursued here have a potential for an arbitrarily high degree of non-compatibility.
arXiv Detail & Related papers (2021-01-14T08:48:44Z) - Commutative d-Torsion K-Theory and Its Applications [0.0]
Commutative $d$-torsion $K$-theory is a variant of topological $K$-theory constructed from unitary matrices of order dividing $d$.
We modify commutative $d$-torsion $K$-theory into a cohomology theory which can be used for studying operator solutions of linear constraint systems.
arXiv Detail & Related papers (2020-06-13T03:13:28Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
We show that a quantum algorithm can be solved by making $2O(k)$ queries to the inputs.
For any constant $varepsilon>0$, this gives a $O(1)$ vs. $N2/3-varepsilon$ separation.
arXiv Detail & Related papers (2019-12-29T01:42:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.