Related papers: Boolean Matching Reversible Circuits: Algorithm and Complexity

Boolean Matching Reversible Circuits: Algorithm and Complexity

URL: http://arxiv.org/abs/2404.12184v1
Date: Thu, 18 Apr 2024 13:47:17 GMT
Title: Boolean Matching Reversible Circuits: Algorithm and Complexity
Authors: Tian-Fu Chen, Jie-Hong R. Jiang,
Abstract summary: We show that the equivalence up to input negation and permutation is reversible in quantum time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving automation problems.
Score: 16.397487896227766
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Boolean matching is an important problem in logic synthesis and verification. Despite being well-studied for conventional Boolean circuits, its treatment for reversible logic circuits remains largely, if not completely, missing. This work provides the first such study. Given two (black-box) reversible logic circuits that are promised to be matchable, we check their equivalences under various input/output negation and permutation conditions subject to the availability/unavailability of their inverse circuits. Notably, among other results, we show that the equivalence up to input negation and permutation is solvable in quantum polynomial time, while its classical complexity is exponential. This result is arguably the first demonstration of quantum exponential speedup in solving design automation problems. Also, as a negative result, we show that the equivalence up to both input and output negations is not solvable in quantum polynomial time unless UNIQUE-SAT is, which is unlikely. This work paves the theoretical foundation of Boolean matching reversible circuits for potential applications, e.g., in quantum circuit synthesis.

Related papers

Experimental Demonstration of Logical Magic State Distillation [62.77974948443222]
We present the experimental realization of magic state distillation with logical qubits on a neutral-atom quantum computer. Our approach makes use of a dynamically reconfigurable architecture to encode and perform quantum operations on many logical qubits in parallel.
arXiv Detail & Related papers (2024-12-19T18:38:46Z)
Circuit Transformer: A Transformer That Preserves Logical Equivalence [20.8279111910994]
We introduce a generative neural model, the "Circuit Transformer", which produces logic circuits strictly equivalent to given Boolean functions. A Markov decision process formulation is also proposed for optimizing certain objectives of circuits.
arXiv Detail & Related papers (2024-03-14T03:24:14Z)
Error-corrected Hadamard gate simulated at the circuit level [42.002147097239444]
We simulate the logical Hadamard gate in the surface code under a circuit-level noise model. Our paper is the first to do this for a unitary gate on a quantum error-correction code.
arXiv Detail & Related papers (2023-12-18T19:00:00Z)
A Generalized Space-Efficient Algorithm for Quantum Bit String Comparators [0.0]
We introduce a design for the comparison of two $n$-qubit logic states using just two ancillary bits. The work allows for sufficient flexibility in the design of quantum algorithms, which can accelerate quantum algorithm development.
arXiv Detail & Related papers (2023-11-11T14:01:35Z)
A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
Inspired by Solomonoffs theory of inductive inference, we propose a prior based on circuit complexity. We argue that an inductive bias towards simple explanations as measured by circuit complexity is appropriate for this problem.
arXiv Detail & Related papers (2023-06-25T01:30:37Z)
One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
arXiv Detail & Related papers (2023-01-05T11:05:22Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
Single-qubit gate teleportation provides a quantum advantage [0.0]
Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates.
arXiv Detail & Related papers (2022-09-28T15:11:39Z)
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)
A Complete Equational Theory for Quantum Circuits [58.720142291102135]
We introduce the first complete equational theory for quantum circuits. Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
arXiv Detail & Related papers (2022-06-21T17:56:31Z)
LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits [58.720142291102135]
We introduce the LOv-calculus, a graphical language for reasoning about linear optical quantum circuits. Two LOv-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LOv-calculus.
arXiv Detail & Related papers (2022-04-25T16:59:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.