arXiv:2111.03862

How to check universality of quantum gates?

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

Published Nov 6, 2021• 2 citations

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

Physical Review AMay 12, 202211 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.00547Physical Review AJun 5, 201727 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

arXiv:quant-ph/0108062Aug 13, 20010 citations

Exact universality from any entangling gate without inverses

Aram W. Harrow

Quantum Information and ComputationSep 1, 20099 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.05780Annales Henri PoincaréAug 10, 201735 citations

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

Piotr Dulian, Adam Sawicki

arXiv:2202.05371QuantumApr 20, 20233 citations

arXiv:2111.03862

How to check universality of quantum gates?

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

Published Nov 6, 2021• 2 citations

arXiv HTML PDF

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$ .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 AMay 12, 202211 citations

Criteria for universality of quantum gates

Adam Sawicki, Katarzyna Karnas

arXiv:1610.00547Physical Review AJun 5, 201727 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.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/0108062Aug 13, 20010 citations

Exact universality from any entangling gate without inverses

Aram W. Harrow

This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V † was given, or when approximate universality was demanded. A common situation in quantum computing is that we can apply only a limited set S ⊂ Ud of unitary gates to some d-dimensional system. The first question we want to ask in this situation is whether gates from S can (approximately) generate any gate in PUd = Ud/U1 (the set of all d × d unitary matrices up to an overall phase). When this is possible, we say that S is (approximately) universal. See [1, 3, 4, 7] for original work on this subject, or Sect 4.5 of [9] or Chapter 8 of [8] for reviews. Formally, S is universal (for PUd) if, for all W ∈ PUd, there exists U1,...,Uk ∈ S such that W = UkUk−1 · · · U2U1, whereas U is approximately universal (for PUd) if, for all W ∈ PUd and all ǫ> 0, there exists U1,...,Uk ∈ S such that d(W,UkUk−1 · · · U2U1) < ǫ. (1) Here d(·, ·) can be any metric, but for concreteness we will take it to be the PUd analogue of operator distance: 〈ψ|U d(U,V): = 1 − infThis note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V † was given, or when approximate universality was demanded. A common situation in quantum computing is that we can apply only a limited set S ⊂ Ud of unitary gates to some d-dimensional system. The first question we want to ask in this situation is whether gates from S can (approximately) generate any gate in PUd = Ud/U1 (the set of all d × d unitary matrices up to an overall phase). When this is possible, we say that S is (approximately) universal. See [1, 3, 4, 7] for original work on this subject, or Sect 4.5 of [9] or Chapter 8 of [8] for reviews. Formally, S is universal (for PUd) if, for all W ∈ PUd, there exists U1,...,Uk ∈ S such that W = UkUk−1 · · · U2U1, whereas U is approximately universal (for PUd) if, for all W ∈ PUd and all ǫ> 0, there exists U1,...,Uk ∈ S such that d(W,UkUk−1 · · · U2U1) < ǫ. (1) Here d(·, ·) can be any metric, but for concreteness we will take it to be the PUd analogue of operator distance: 〈ψ|U d(U,V): = 1 − inf

Quantum Information and ComputationSep 1, 20099 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.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.05780Annales Henri PoincaréAug 10, 201735 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.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.05371QuantumApr 20, 20233 citations

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.

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

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.