Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2111.03862

How to check universality of quantum gates?

Adam Sawicki, Lorenzo Mattioli, Zoltán Zimborás

Published Nov 6, 2021• 5 citations
arXivHTMLPDF

Abstract

We provide two simple universality criteria. Our first criterion states that $\mathcal{S}\subset G_d:=U(d)$ is universal if and only if $\mathcal{S}$ forms a $δ$-approximate $t(d)$-design, where $t(2)=6$ and $t(d)=4$ for $d\geq3$. Our second universality criterion says that $\mathcal{S}\subset G_d$ is universal if and only if the centralizer of $\mathcal{S}^{t(d),t(d)}=\{U^{\otimes t(d)}\otimes \bar{U}^{\otimes t(d)}|U\in \mathcal{S}\}$ is equal to the centralizer of $G_d^{t(d),t(d)}=\{U^{\otimes t(d)}\otimes \bar{U}^{\otimes t(d)}|U\in G_d\}$, where $t(2)=3$, and $t(d)=2$ for $d\geq 3$. The equality of the centralizers can be verified by comparing their dimensions.

DOI
10.48550/arxiv.2111.03862

Related papers

Universality verification for a set of quantum gates

Adam Sawicki, Lorenzo Mattioli, Zoltán Zimborás

We establish a relationship between the notion of universal quantum gates and the notion of unitary $t$-designs. We show that a set of qudit gates $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if $\mathcal{S}$ forms a $\ensuremath{\delta}$-approximate $t(d)$-design, where $\ensuremath{\delta}<1, t(2)=6$, and $t(d)=4$ for $d\ensuremath{\ge}3$. Moreover, we argue that from the application point of view sets $\mathcal{S}$ with the $\ensuremath{\delta}$ close to 1 should be regarded as nonuniversal. We also provide a second, more algebraic, criterion for the universality verification. It says that $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if the matrices that commute with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}\mathcal{S}}$ commute also with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}U(d)}$, where $t(2)=3$, and $t(d)=2$ for $d\ensuremath{\ge}3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension $d$.

Physical Review A•May 12, 2022•14 citations

Criteria for universality of quantum gates

Adam Sawicki, Katarzyna Karnas

Compact-form criteria are provided for deciding universality of a given set of gates in a finite number of steps. The criteria may also indicate what types of gates can be added to a set of nonuniversal gates to turn it into a universal set.

arXiv:1610.00547•Physical Review A•Jun 5, 2017•26 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

In this paper we study universality for quantum gates acting on qudits.Qudits are states in a Hilbert space of dimension d where d is at least two. We determine which 2-qudit gates V have the properties (i) the collection of all 1-qudit gates together with V produces all n-qudit gates up to arbitrary precision, or (ii) the collection of all 1-qudit gates together with V produces all n-qudit gates exactly. We show that (i) and (ii) are equivalent conditions on V, and they hold if and only if V is not a primitive gate. Here we say V is primitive if it transforms any decomposable tensor into a decomposable tensor. We discuss some applications and also relations with work of other authors.

arXiv:quant-ph/0108062•Aug 13, 2001•96 citations

Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Piotr Dulian, Adam Sawicki

For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog⁡(d)−log⁡(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.

arXiv:2202.05371•Quantum•Apr 20, 2023•6 citations

Universality of Single-Qudit Gates

Adam Sawicki, Katarzyna Karnas

We consider the problem of deciding if a set of quantum one-qudit gates $$\mathcal {S}=\{g_1,\ldots ,g_n\}\subset G$$ is universal, i.e. if $${<}\mathcal {S}{>}$$ is dense in G, where G is either the special unitary or the special orthogonal group. To every gate g in $$\mathcal {S}$$ we assign the orthogonal matrix $$\mathrm {Ad}_g$$ that is image of g under the adjoint representation $$\mathrm {Ad}:G\rightarrow SO(\mathfrak {g})$$ and $$\mathfrak {g}$$ is the Lie algebra of G. The necessary condition for the universality of $$\mathcal {S}$$ is that the only matrices that commute with all $$\mathrm {Ad}_{g_i}$$ ’s are proportional to the identity. If in addition there is an element in $${<}\mathcal {S}{>}$$ whose Hilbert–Schmidt distance from the centre of G belongs to $$]0,\frac{1}{\sqrt{2}}[$$ , then $$\mathcal {S}$$ is universal. Using these we provide a simple algorithm that allows deciding the universality of any set of d-dimensional gates in a finite number of steps and formulate a general classification theorem.

arXiv:1609.05780•Annales Henri Poincaré•Aug 10, 2017•36 citations

About Weyl and Wigner Tomography in Finite-Dimensional Hilbert Spaces

Thomas Durt

We study different techniques that allow us to gain complete knowledge about an unknown quantum state, e.g. to perform full tomography of this state. In a first time, we focus on two simple cases, full tomography of one- and two-qubit systems. We analyze and compare those techniques according to two criteria. Our first criterion is the minimisation of the redundancy of the data acquired during the tomographic process. In the case of two-qubits tomography, we also analyze this process from the point of view of factorisability, so to say we analyze the possibility to realise the tomographic process through local operations and classical communications between local observers. Finally, we present new results that concern the extension of the one- and two-qubit cases to higher dimensions.

arXiv:quant-ph/0604117•Open Systems & Information Dynamics•Nov 15, 2006•21 citations
We provide two simple universality criteria. Our first criterion states that S⊂Gd:=U(d)\mathcal{S}\subset G_d:=U(d)S⊂Gd​:=U(d) is universal if and only if S\mathcal{S}S forms a δδδ-approximate t(d)t(d)t(d)-design, where t(2)=6t(2)=6t(2)=6 and t(d)=4t(d)=4t(d)=4 for d≥3d\geq3d≥3. Our second universality criterion says that S⊂Gd\mathcal{S}\subset G_dS⊂Gd​ is universal if and only if the centralizer of St(d),t(d)={U⊗t(d)⊗Uˉ⊗t(d)∣U∈S}\mathcal{S}^{t(d),t(d)}=\{U^{\otimes t(d)}\otimes \bar{U}^{\otimes t(d)}|U\in \mathcal{S}\}St(d),t(d)={U⊗t(d)⊗Uˉ⊗t(d)∣U∈S} is equal to the centralizer of Gdt(d),t(d)={U⊗t(d)⊗Uˉ⊗t(d)∣U∈Gd}G_d^{t(d),t(d)}=\{U^{\otimes t(d)}\otimes \bar{U}^{\otimes t(d)}|U\in G_d\}Gdt(d),t(d)​={U⊗t(d)⊗Uˉ⊗t(d)∣U∈Gd​}, where t(2)=3t(2)=3t(2)=3, and t(d)=2t(d)=2t(d)=2 for d≥3d\geq 3d≥3. The equality of the centralizers can be verified by comparing their dimensions.
We establish a relationship between the notion of universal quantum gates and the notion of unitary ttt-designs. We show that a set of qudit gates $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if S\mathcal{S}S forms a $\ensuremath{\delta}$-approximate t(d)t(d)t(d)-design, where $\ensuremath{\delta}<1, t(2)=6$, and t(d)=4t(d)=4t(d)=4 for $d\ensuremath{\ge}3$. Moreover, we argue that from the application point of view sets S\mathcal{S}S with the $\ensuremath{\delta}$ close to 1 should be regarded as nonuniversal. We also provide a second, more algebraic, criterion for the universality verification. It says that $\mathcal{S}\ensuremath{\subset}U(d)$ is universal if and only if the matrices that commute with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}\mathcal{S}}$ commute also with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}U(d)}$, where t(2)=3t(2)=3t(2)=3, and t(d)=2t(d)=2t(d)=2 for $d\ensuremath{\ge}3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension ddd.
In this paper we study universality for quantum gates acting on qudits.Qudits are states in a Hilbert space of dimension d where d is at least two. We determine which 2-qudit gates V have the properties (i) the collection of all 1-qudit gates together with V produces all n-qudit gates up to arbitrary precision, or (ii) the collection of all 1-qudit gates together with V produces all n-qudit gates exactly. We show that (i) and (ii) are equivalent conditions on V, and they hold if and only if V is not a primitive gate. Here we say V is primitive if it transforms any decomposable tensor into a decomposable tensor. We discuss some applications and also relations with work of other authors.
For a random set S⊂U(d) of quantum gates we provide bounds on the probability that S forms a δ -approximate t -design. In particular we have found that for S drawn from an exact t -design the probability that it forms a δ -approximate t -design satisfies the inequality P(δ≥x)≤2Dte−|S|xarctanh(x)(1−x2)|S|/2=O(2Dt(e−x21−x2)|S|) , where Dt is a sum over dimensions of unique irreducible representations appearing in the decomposition of U↦U⊗t⊗U¯⊗t . We use our results to show that to obtain a δ -approximate t -design with probability P one needs O(δ−2(tlog⁡(d)−log⁡(1−P))) many random gates. We also analyze how δ concentrates around its expected value Eδ for random S . Our results are valid for both symmetric and non-symmetric sets of gates.
We consider the problem of deciding if a set of quantum one-qudit gates S={g1,…,gn}⊂G\mathcal {S}=\{g_1,\ldots ,g_n\}\subset GS={g1​,…,gn​}⊂G is universal, i.e. if <S>{<}\mathcal {S}{>}<S> is dense in G, where G is either the special unitary or the special orthogonal group. To every gate g in S\mathcal {S}S we assign the orthogonal matrix Adg\mathrm {Ad}_gAdg​ that is image of g under the adjoint representation Ad:G→SO(g)\mathrm {Ad}:G\rightarrow SO(\mathfrak {g})Ad:G→SO(g) and g\mathfrak {g}g is the Lie algebra of G. The necessary condition for the universality of S\mathcal {S}S is that the only matrices that commute with all Adgi\mathrm {Ad}_{g_i}Adgi​​ ’s are proportional to the identity. If in addition there is an element in <S>{<}\mathcal {S}{>}<S> whose Hilbert–Schmidt distance from the centre of G belongs to ]0,12[]0,\frac{1}{\sqrt{2}}[]0,2​1​[ , then S\mathcal {S}S is universal. Using these we provide a simple algorithm that allows deciding the universality of any set of d-dimensional gates in a finite number of steps and formulate a general classification theorem.
We study different techniques that allow us to gain complete knowledge about an unknown quantum state, e.g. to perform full tomography of this state. In a first time, we focus on two simple cases, full tomography of one- and two-qubit systems. We analyze and compare those techniques according to two criteria. Our first criterion is the minimisation of the redundancy of the data acquired during the tomographic process. In the case of two-qubits tomography, we also analyze this process from the point of view of factorisability, so to say we analyze the possibility to realise the tomographic process through local operations and classical communications between local observers. Finally, we present new results that concern the extension of the one- and two-qubit cases to higher dimensions.