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
• Authors: Timothy Proctor and Kevin Young
• 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

• 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)
• 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.