Minimum Synthesis Cost of CNOT Circuits

• URL: http://arxiv.org/abs/2408.07898v1
• Date: Thu, 15 Aug 2024 03:09:53 GMT
• Title: Minimum Synthesis Cost of CNOT Circuits
• Authors: Alan Bu, Evan Fan, Robert Sanghyeon Joo,
• Abstract summary: We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(nomega)$ time. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimizing the size and depth of CNOT circuits is an active area of research in quantum computing and is particularly relevant for circuits synthesized from the Clifford + T universal gate set. Although many techniques exist for finding short syntheses, it is difficult to assess how close to optimal these syntheses are without an exponential brute-force search. We use a novel method of categorizing CNOT gates in a synthesis to obtain a strict lower bound computable in $O(n^{\omega})$ time on the minimum number of gates needed to synthesize a given CNOT circuit, where $\omega$ denotes the matrix multiplication constant and $n$ is the number of qubits involved. Applying our framework, we prove that $3(n-1)$ gate syntheses of the $n$-cycle circuit are optimal and provide insight into their structure. We also generalize this result to permutation circuits. For linear reversible circuits with $ n = 3, 4, 5$ qubits, our lower bound is optimal for 100%, 67.7%, and 23.1% of circuits and is accurate to within one CNOT gate in 100%, 99.5%, and 83.0% of circuits respectively. We also introduce an algorithm that efficiently determines whether certain circuits can be synthesized with fewer than $n$ CNOT gates.

Related papers

• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Lower $T$-count with faster algorithms [3.129187821625805]
  We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times. We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
  arXiv  Detail & Related papers  (2024-07-11T17:31:20Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Global Synthesis of CNOT Circuits with Holes [0.0]
  We propose an alternative approach to generalising resynthesis algorithms to general quantum circuits. Instead of cutting the circuit into slices, we "cut out" the gates we can't resynthesise leaving holes in our quantum circuit. The result is a second-order process called a quantum comb, which can be resynthesised directly.
  arXiv  Detail & Related papers  (2023-08-31T06:58:03Z)
• Towards a generic compilation approach for quantum circuits through resynthesis [0.0]
  We use an intermediate representation consisting of Paulistrings over Z, I and X, I called a mixed ZX-phase. From this universal representation, we generate a completely new circuit such that all multi-qubit gates (CNOTs) are satisfying a given quantum architecture.
  arXiv  Detail & Related papers  (2023-04-18T08:25:47Z)
• Asymptotically optimal synthesis of reversible circuits [0.0]
  We propose an algorithm to implement an arbitrary $n$wire circuit with no more than $ (2n n/log n)$ elementary gates.
  arXiv  Detail & Related papers  (2023-02-13T03:08:55Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states. We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
  arXiv  Detail & Related papers  (2022-02-23T04:19:57Z)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• SAT-based Circuit Local Improvement [77.36158507255637]
  Finding exact circuit size is a notorious optimization problem in practice. We search for a smaller circuit in a ball around a given circuit. We report the results of experiments with various symmetric functions.
  arXiv  Detail & Related papers  (2021-02-19T16:01:50Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.