Related papers: Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits

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)
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)
Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
arXiv Detail & Related papers (2022-08-12T15:05:07Z)
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.