Physical Review A

Universality verification for a set of quantum gates

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

Published May 12, 2022• 11 citations

Abstract

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$.

DOI: 10.1103/physreva.105.052602

Related papers

How to check universality of quantum gates?

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

arXiv:2111.03862Nov 6, 20212 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

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

arXiv:2007.10885IEEE Transactions on Information TheoryNov 13, 202127 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

Computational matematics series/Computational mathematics seriesFeb 14, 200285 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

Chapman & Hall/CRC eBooksFeb 14, 2002185 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

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

Physical Review A

Universality verification for a set of quantum gates

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

Published May 12, 2022• 11 citations

Publisher

Abstract

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

DOI: 10.1103/physreva.105.052602

Related papers

How to check universality of quantum gates?

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

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

arXiv:2111.03862Nov 6, 20212 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

Epsilon-Nets, Unitary Designs, and Random Quantum Circuits

Michał Oszmaniec, Adam Sawicki, Michał Horodecki

Epsilon-nets and approximate unitary $t$ -designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for $d$ dimensional Hilbert space, unitaries constituting$\delta $-approximate$ t $-expanders form$ \epsilon $-nets for$ t\simeq \frac {d^{5/2}}{ \epsilon } $and$ \delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}} $. We also show that for arbitrary$ t $,$ \epsilon $-nets can be used to construct$ \delta $-approximate unitary$ t $-designs for$ \delta \simeq \epsilon t $, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$ t $design necessary to obtain an$ \epsilon $-net must grow at least as fast as$ \frac {1}{ \epsilon } $(for fixed dimension) and not slower than$ d^{2} $(for fixed$ \epsilon $). This shows near optimality of our result connecting$ t $-designs and$ \epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

arXiv:2007.10885IEEE Transactions on Information TheoryNov 13, 202127 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 can be any integer ≥ 2. 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 can be any integer ≥ 2. 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.

Computational matematics series/Computational mathematics seriesFeb 14, 200285 citations

Universal quantum gates

Jean-Luc Brylinski, Ranee Kathryn Brylinski

Abstract In this paper we study universality for quantum gates acting on qudits. Qudits are states in a Hilbert space of dimension d where d can be any integer ≥ 2. 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.Abstract In this paper we study universality for quantum gates acting on qudits. Qudits are states in a Hilbert space of dimension d where d can be any integer ≥ 2. 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.

Chapman & Hall/CRC eBooksFeb 14, 2002185 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

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

Epsilon-nets and approximate unitary

t

-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for

d

dimensional Hilbert space, unitaries constituting$\delta

-approximate

-expanders form

\epsilon

-nets for

t\simeq \frac {d^{5/2}}{ \epsilon }

and

\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}

. We also show that for arbitrary

,

\epsilon

-nets can be used to construct

\delta

-approximate unitary

-designs for

\delta \simeq \epsilon t

, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary

design necessary to obtain an

\epsilon

-net must grow at least as fast as

\frac {1}{ \epsilon }

(for fixed dimension) and not slower than

d^{2}

(for fixed

\epsilon

). This shows near optimality of our result connecting

-designs and

\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.