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

• Multi-strategy Based Quantum Cost Reduction of Quantum Boolean Circuits [0.4999814847776098]
  The construction of quantum computers is based on the synthesis of low-cost quantum circuits. This paper proposes two algorithms to construct a quantum circuit for any Boolean function expressed in a Positive Polarity Reed-Muller $PPRM$ expansion.
  arXiv  Detail & Related papers  (2024-07-05T19:25:46Z)
• 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)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)

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.