Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits

• URL: http://arxiv.org/abs/2311.07741v2
• Date: Fri, 12 Apr 2024 19:52:59 GMT
• Title: Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits
• Authors: Matthew Amy, Andrew N. Glaudell, Shaun Kelso, William Maxwell, Samuel S. Mendelson, Neil J. Ross,
• Abstract summary: We show that when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $mathcalG_n$. We moreover show that $log(n)-2$ ancillas are always sufficient to construct a circuit for $U$.
• Score: 0.8411424745913132
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $n\geq 8$ be divisible by 4. The Clifford-cyclotomic gate set $\mathcal{G}_n$ is the universal gate set obtained by extending the Clifford gates with the $z$-rotation $T_n = \mathrm{diag}(1,\zeta_n)$, where $\zeta_n$ is a primitive $n$-th root of unity. In this note, we show that, when $n$ is a power of 2, a multiqubit unitary matrix $U$ can be exactly represented by a circuit over $\mathcal{G}_n$ if and only if the entries of $U$ belong to the ring $\mathbb{Z}[1/2,\zeta_n]$. We moreover show that $\log(n)-2$ ancillas are always sufficient to construct a circuit for $U$. Our results generalize prior work to an infinite family of gate sets and show that the limitations that apply to single-qubit unitaries, for which the correspondence between Clifford-cyclotomic operators and matrices over $\mathbb{Z}[1/2,\zeta_n]$ fails for all but finitely many values of $n$, can be overcome through the use of ancillas.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits [0.0]
  We prove that a $3ntimes 3n$ unitary matrix $U$ can be represented by an $n$-qutrit circuit over the Clifford-cyclotomic gate set of degree $3k$.
  arXiv  Detail & Related papers  (2024-05-13T19:27:48Z)
• Quantum charges of harmonic oscillators [55.2480439325792]
  We show that the energy eigenfunctions $psi_n$ with $nge 1$ are complex coordinates on orbifolds $mathbbR2/mathbbZ_n$. We also discuss "antioscillators" with opposite quantum charges and the same positive energy.
  arXiv  Detail & Related papers  (2024-04-02T09:16:18Z)
• Synthesis and Arithmetic of Single Qutrit Circuits [0.9208007322096532]
  We study single qutrit quantum circuits consisting of words over the Clifford+ $mathcalD$ gate set. We characterize classes of qutrit unit vectors $z$ with entries in $mathbbZ[xi, frac1chi]$.
  arXiv  Detail & Related papers  (2023-11-15T04:50:41Z)
• On character table of Clifford groups [0.0]
  We construct the character table of the Clifford group $mathcalC_n$ for $n=1,2,3$. As an application, we can efficiently decompose the (higher power of) tensor product of the matrix representation. As a byproduct, we give a presentation of the finite symplectic group $Sp(2n,2)$ in terms of generators and relations.
  arXiv  Detail & Related papers  (2023-09-26T11:29:35Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  An algorithm for reversible logic synthesis is proposed. Map can be written as a tensor product of a rank-($2n-2$) tensor and the $2times 2$ identity matrix.
  arXiv  Detail & Related papers  (2021-07-09T08:18:53Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.