A simple asymptotically optimal Clifford circuit compilation algorithm

• URL: http://arxiv.org/abs/2310.10882v1
• Date: Mon, 16 Oct 2023 23:27:59 GMT
• Title: A simple asymptotically optimal Clifford circuit compilation algorithm
• Abstract summary: We present an algorithm that decomposes any $n$-qubit Clifford operator into a circuit consisting of three subcircuits. As with other derivationally optimal Clifford compilation algorithms, the resulting circuit contains $O(n2/log n)$ two-qubit gates.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an algorithm that decomposes any $n$-qubit Clifford operator into a circuit consisting of three subcircuits containing only CNOT or CPHASE gates with layers of one-qubit gates before and after each of these subcircuits. As with other asymptotically optimal Clifford compilation algorithms, the resulting circuit contains $O(n^2/\log n)$ two-qubit gates. The derivation of our algorithm only requires the symplectic representation of Clifford gates, basic row and column matrix manipulations, and some known properties of general matrices over 0 and 1.

Related papers

• Link-middle-cut lower bounds for Clifford circuit synthesis [0.0]
  Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization.<n>We extend the link--middle-cut (LMC) framework for linear circuits to Clifford operators represented by binary symplectic tableaux.
  arXiv  Detail & Related papers  (2026-09-14T18:42:19Z)
• Direct U(2) approximation via repeat-until-success circuits [0.0]
  We show how to approximate arbitrary one-qubit unitaries, bypassing the Euler decomposition and the magnitude approximation problem.<n>Our technique also applies to approximating unitaries with multi-qubit gate sets such as Clifford and CS, or Clifford and CCZ, as well as to approximating matrices using multi-qubit gate sets such as Real Clifford and CCZ.
  arXiv  Detail & Related papers  (2026-04-21T22:35:49Z)
• Improved quantum circuits for division [42.76841620787673]
  We develop new fault-tolerant quantum circuits for various integer division algorithms.<n> circuits achieve an up to 76.08% and 68.35% reduction in T-count and CNOT-count.
  arXiv  Detail & Related papers  (2026-03-18T13:41:43Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• A Complete Equational Theory for Real-Clifford+CH Quantum Circuits [51.56484100374058]
  We give a simple set of equalities between circuits of this fragment, and prove that any other true equation can be derived from these.<n>This is the first such completeness result for a finitely-generated, universal fragment of quantum circuits, with no parameterized gates and no need for ancillas.
  arXiv  Detail & Related papers  (2026-02-06T12:11:39Z)
• Prefix Sums via Kronecker Products [47.600794349481966]
  We show how to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.<n>As an application, we show how to use these circuits to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.
  arXiv  Detail & Related papers  (2025-12-18T08:49:18Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [44.99833362998488]
  We use global interactions, such as the Global Molmer-Sorensen gate present in ion trap hardware, to optimize and synthesize quantum circuits.<n>The algorithm is based on the ZX-calculus and uses a specialized circuit extraction routine that groups entangling gates into Global MolmerSorensen gates.<n>We benchmark the algorithm in a variety of circuits, and show how it improves their performance under state-of-the-art hardware considerations.
  arXiv  Detail & Related papers  (2025-07-28T10:25:31Z)
• Heuristic and Optimal Synthesis of CNOT and Clifford Circuits [3.1952340441132474]
  Linear reversible circuits, equivalent to circuits composed of CNOT gates, have important applications in classical computing. We present methods for CNOT and general Clifford circuit synthesis which can be used to minimise either the entangling two-qubit gate count or the circuit depth. The algorithms have been implemented in a GitHub repository for use by the classical and quantum computing community.
  arXiv  Detail & Related papers  (2025-03-18T19:09:58Z)
• Targeted Clifford logical gates for hypergraph product codes [61.269295538188636]
  We construct explicit targeted logical gates for hypergraph product codes. As a concrete example, we give logical circuits for the $[[18,2,3]]$ toric code.
  arXiv  Detail & Related papers  (2024-11-26T02:32:44Z)
• Multi-qubit circuit synthesis and Hermitian lattices [0.0]
  We present new optimal and synthesis algorithms for exact synthesis of multi-qubit unitaries and isometries. The optimal algorithms are the A* search instantiated with a new data structure for graph and new consistent functions.
  arXiv  Detail & Related papers  (2024-05-29T17:27:50Z)
• Automatically Identifying Local and Global Circuits with Linear Computation Graphs [45.760716193942685]
  We introduce our circuit discovery pipeline with Sparse Autoencoders (SAEs) and a variant called Transcoders. Our methods do not require linear approximation to compute the causal effect of each node. We analyze three kinds of circuits in GPT-2 Small: bracket, induction, and Indirect Object Identification circuits.
  arXiv  Detail & Related papers  (2024-05-22T17:50:04Z)
• Multi-qutrit exact synthesis [0.0]
  We present an exact synthesis algorithm for qutrit unitaries in $mathcalU_3n(mathbbZ[/3,e2pi i/3])$ over the Clifford$+T$ gate set with at most one ancilla. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford$+mathcalD$ over the multi-qutrit Clifford$+T$ gate set with at most two ancillas.
  arXiv  Detail & Related papers  (2024-05-13T19:48:10Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05: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)
• Decomposition of Clifford Gates [3.7900158137749322]
  We provide a fast algorithm that decomposes any Clifford gate as a $textitminimal$ product of Clifford transvections. The algorithm can be directly used for finding all Pauli matrices that commute with any given Clifford gate.
  arXiv  Detail & Related papers  (2021-02-05T10:32:09Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• A simple method for sampling random Clifford operators [1.0587959762260986]
  We describe a simple algorithm for sampling $n$-qubit Clifford operators uniformly at random. The algorithm outputs the Clifford operators in the form of quantum circuits with at most $5n + 2n2$ elementary gates and a maximum depth of $mathcalO(nlog n)$ on fully connected topologies.
  arXiv  Detail & Related papers  (2020-08-13T16:56:42Z)
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz [68.8204255655161]
  We describe a compilation strategy for Variational Quantum Eigensolver (VQE) algorithms. We use the Unitary Coupled Cluster (UCC) ansatz to reduce circuit depth and gate count.
  arXiv  Detail & Related papers  (2020-07-20T22:26:16Z)
• 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)
• Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation [0.0]
  We study two-qubit circuits over the Clifford+CS gate set. We introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators.
  arXiv  Detail & Related papers  (2020-01-16T18:55:38Z)

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.