A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit
- URL: http://arxiv.org/abs/2209.05470v1
- Date: Thu, 8 Sep 2022 17:55:30 GMT
- Title: A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit
- Authors: Alexander Feldman, Johan de Kleer, Ion Matei
- Abstract summary: 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.
- Score: 73.70667578066775
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Faults are stochastic by nature while most man-made systems, and especially
computers, work deterministically. This necessitates the linking of probability
theory with mathematical logics, automata, and switching circuit theory. This
paper provides such a connecting via quantum information theory which is an
intuitive approach as quantum physics obeys probability laws. In this paper we
provide a novel approach for computing diagnosis of switching circuits with
gate-based quantum computers. The approach is based on the idea of putting the
qubits representing faults in superposition and compute all, often
exponentially many, diagnoses simultaneously. We empirically compare the
quantum algorithm for diagnostics to an approach based on SAT and
model-counting. For a benchmark of combinational circuits we establish an error
of less than one percent in estimating the true probability of faults.
Related papers
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - Tailoring Fault-Tolerance to Quantum Algorithms [3.836669717540222]
We develop a solve-and-stitch algorithm to synthesize physical realizations of Clifford Trotter circuits.
We achieve fault-tolerance for these circuits using flag gadgets, which add minimal overhead.
arXiv Detail & Related papers (2024-04-18T07:15:15Z) - Realization of quantum algorithms with qudits [0.7892577704654171]
We review several ideas indicating how multilevel quantum systems, also known as qudits, can be used for efficient realization of quantum algorithms.
We focus on techniques of leveraging qudits for simplifying decomposition of multiqubit gates, and for compressing quantum information by encoding multiple qubits in a single qudit.
These theoretical schemes can be implemented with quantum computing platforms of various nature, such as trapped ions, neutral atoms, superconducting junctions, and quantum light.
arXiv Detail & Related papers (2023-11-20T18:34:19Z) - Visualizing Quantum Circuit Probability -- estimating computational
action for quantum program synthesis [0.0]
The probability of states in the circuit model of computation is defined.
The reachability and expressibility in a space-time-bounded setting for classical and quantum gate sets are enumerated and visualized.
The article suggests how applications like geometric quantum machine learning, novel quantum algorithm and quantum artificial general intelligence can benefit from studying circuit probabilities.
arXiv Detail & Related papers (2023-04-05T10:49:36Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Establishing trust in quantum computations [0.0]
We introduce a technique for measuring the fidelity with which an as-built quantum computer can execute an algorithm.
Our technique converts the algorithm's quantum circuits into a set of closely related circuits whose success rates can be efficiently measured.
arXiv Detail & Related papers (2022-04-15T17:44:30Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z) - Electronic structure with direct diagonalization on a D-Wave quantum
annealer [62.997667081978825]
This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer.
We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
arXiv Detail & Related papers (2020-09-02T22:46:47Z) - QUANTIFY: A framework for resource analysis and design verification of
quantum circuits [69.43216268165402]
QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits.
It is based on Google Cirq and is developed with Clifford+T circuits in mind.
For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
arXiv Detail & Related papers (2020-07-21T15:36:25Z)
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.