Quantum t-design

A quantum t-design is a probability distribution over either pure quantum states or unitary operators which can duplicate properties of the probability distribution over the Haar measure for polynomials of degree t or less. Specifically, the average of any polynomial function of degree t over the design is exactly the same as the average over Haar measure. Here the Haar measure is a uniform probability distribution over all quantum states or over all unitary operators. Quantum t-designs are so called because they are analogous to t-designs in classical statistics, which arose historically in connection with the problem of design of experiments. Two particularly important types of t-designs in quantum mechanics are projective and unitary t-designs.^[1]

A spherical design is a collection of points on the unit sphere for which polynomials of bounded degree can be averaged over to obtain the same value that integrating over surface measure on the sphere gives. Spherical and projective t-designs derive their names from the works of Delsarte, Goethals, and Seidel in the late 1970s, but these objects played earlier roles in several branches of mathematics, including numerical integration and number theory. Particular examples of these objects have found uses in quantum information theory,^[2] quantum cryptography, and other related fields.

Unitary t-designs are analogous to spherical designs in that they reproduce the entire unitary group via a finite collection of unitary matrices.^[1] The theory of unitary 2-designs was developed in 2006 ^[1] specifically to achieve a practical means of efficient and scalable randomized benchmarking^[3] to assess the errors in quantum computing operations, called gates. Since then unitary t-designs have been found useful in other areas of quantum computing and more broadly in quantum information theory and applied to problems as far reaching as the black hole information paradox.^[4] Unitary t-designs are especially relevant to randomization tasks in quantum computing since ideal operations are usually represented by unitary operators.

Motivation

In a d-dimensional Hilbert space when averaging over all quantum pure states the natural group is SU(d), the special unitary group of dimension d.^{[citation needed]} The Haar measure is, by definition, the unique group-invariant measure, so it is used to average properties that are not unitarily invariant over all states, or over all unitaries.

A particularly widely used example of this is the spin ${\displaystyle {\tfrac {1}{2}}}$ system. For this system the relevant group is SU(2) which is the group of all 2x2 unitary operators with determinant 1. Since every operator in SU(2) is a rotation of the Bloch sphere, the Haar measure for spin-1/2 particles is invariant under all rotations of the Bloch sphere. This implies that the Haar measure is the rotationally invariant measure on the Bloch sphere, which can be thought of as a constant density distribution over the surface of the sphere.

An important class of complex projective t-designs, are symmetric informationally complete positive operator-valued measures (POVMs), which are complex projective 2-design. Since such 2-designs must have at least ${\displaystyle d^{2}}$ elements, a SIC-POVM is a minimal sized complex projective 2-designs.^[5]

Spherical t-Designs

Complex projective t-designs have been studied in quantum information theory as quantum t-designs.^[6] These are closely related to spherical 2t-designs of vectors in the unit sphere in ${\displaystyle \mathbb {R} ^{d}}$ which when naturally embedded in ${\displaystyle \mathbb {C} ^{d}}$ give rise to complex projective t-designs.

Formally, we define a probability distribution over quantum states ${\displaystyle (p_{i},|\phi _{i}\rangle )}$ to be a ^[6] complex projective t-design if

${\displaystyle \sum _{i}p_{i}(|\phi _{i}\rangle \langle \phi _{i}|)^{\otimes t}=\int _{\psi }(|\psi \rangle \langle \psi |)^{\otimes t}d\psi }$

Here, the integral over states is taken over the Haar measure on the unit sphere in ${\displaystyle \mathbb {C} ^{d}}$

Exact t-designs over quantum states cannot be distinguished from the uniform probability distribution over all states when using t copies of a state from the probability distribution. However, in practice even t-designs may be difficult to compute. For this reason approximate t-designs are useful.

Approximate t-designs are most useful due to their ability to be efficiently implemented. i.e. it is possible to generate a quantum state ${\displaystyle |\phi \rangle }$ distributed according to the probability distribution ${\displaystyle p_{i}|\phi _{i}\rangle }$ in ${\displaystyle O(\log ^{c}d)}$ time. This efficient construction also implies that the POVM of the operators ${\displaystyle Np_{i}|\phi _{i}\rangle \langle \phi _{i}|}$ can be implemented in ${\displaystyle O(\log ^{c}d)}$ time.

The technical definition of an approximate t-design is:

If ${\displaystyle \sum _{i}p_{i}|\phi _{i}\rangle \langle \phi _{i}|=\int _{\psi }|\psi \rangle \langle \psi |d\psi }$

and ${\displaystyle (1-\epsilon )\int _{\psi }(|\psi \rangle \langle \psi |)^{\otimes t}d\psi \leq \sum _{i}p_{i}(|\phi _{i}\rangle \langle \phi _{i}|)^{\otimes t}\leq (1+\epsilon )\int _{\psi }(|\psi \rangle \langle \psi |)^{\otimes t}d\psi }$

then ${\displaystyle (p_{i},|\phi _{i}\rangle )}$ is an ${\displaystyle \epsilon }$-approximate t-design.

It is possible, though perhaps inefficient, to find an ${\displaystyle \epsilon }$-approximate t-design consisting of quantum pure states for a fixed t.

Construction

For convenience d is assumed to be a power of 2.

Using the fact that for any d there exists a set of ${\displaystyle N^{d}}$ functions {0,...,d-1} ${\displaystyle \rightarrow }$ {0,...,d-1} such that for any distinct ${\displaystyle k_{1},...,k_{N}\in }$ {0,...,d-1} the image under f, where f is chosen at random from S, is exactly the uniform distribution over tuples of N elements of {0,...,d-1}.

Let ${\displaystyle |\psi \rangle =\sum _{i=1}^{d}\alpha _{i}|i\rangle }$ be drawn from the Haar measure. Let ${\displaystyle P_{d}}$ be the probability distribution of ${\displaystyle \alpha _{1}}$ and let ${\displaystyle P=\lim _{d\rightarrow \infty }{\sqrt {d}}P_{d}}$. Finally let ${\displaystyle \alpha }$ be drawn from P. If we define ${\displaystyle X=|\alpha |}$ with probability ${\displaystyle {\tfrac {1}{2}}}$ and ${\displaystyle X=-|\alpha |}$ with probability ${\displaystyle {\tfrac {1}{2}}}$ then: ${\displaystyle E[X^{j}]=0}$ for odd j and ${\displaystyle E[X^{j}]=({\tfrac {j}{2}})!}$ for even j.

Using this and Gaussian quadrature we can construct ${\displaystyle p_{f,g}={\frac {\sum _{i=1}^{d}a_{f,i}^{2}}{|S_{1}||S_{2}|}}}$ so that ${\displaystyle p_{f,g}|\psi _{f,g}\rangle }$ is an approximate t-design.

Unitary t-Designs

Unitary t-designs are analogous to spherical designs in that they reproduce the entire unitary group via a finite collection of unitary matrices.^[1] The theory of unitary 2-designs was developed in 2006 ^[1] specifically to achieve a practical means of efficient and scalable randomized benchmarking^[3] to assess the errors in quantum computing operations, called gates. Since then unitary t-designs have been found useful in other areas of quantum computing and more broadly in quantum information theory and in fields as far reaching as black hole physics.^[4] Unitary t-designs are especially relevant to randomization tasks in quantum computing since ideal operations are usually represented by unitary operators.

Elements of a unitary t-design are elements of the unitary group, U(d), the group of ${\displaystyle d\times d}$ unitary matrices. A t-design of unitary operators will generate a t-design of states.

Suppose ${\displaystyle {U_{k}}}$ is a unitary t-design (i.e. a set of unitary operators). Then for any pure state ${\displaystyle |\psi \rangle }$ let ${\displaystyle |\psi _{k}\rangle =U_{k}|\psi \rangle }$. Then ${\displaystyle {|\psi _{k}\rangle }}$ will always be a t-design for states.

Formally define a unitary t-design, X, if

${\displaystyle {\frac {1}{|X|}}\sum _{U\in X}U^{\otimes t}\otimes (U^{*})^{\otimes t}=\int _{U(d)}U^{\otimes t}\otimes (U^{*})^{\otimes t}dU}$

Observe that the space linearly spanned by the matrices ${\displaystyle U^{\otimes r}\otimes (U^{*})^{\otimes s}dU}$ over all choices of U is identical to the restriction ${\displaystyle U\in X}$ and ${\displaystyle r+s=t}$ This observation leads to a conclusion about the duality between unitary designs and unitary codes.

Using the permutation maps it is possible^[6] to verify directly that a set of unitary matrices forms a t-design.^[7]

One direct result of this is that for any finite ${\displaystyle X\subseteq U(d)}$

${\displaystyle {\frac {1}{|X|^{2}}}\sum _{U,V\in X}|\operatorname {tr} (U*V)|^{2t}\geq \int _{U(d)}|\operatorname {tr} (U*V)|^{2t}dU}$

With equality if and only if X is a t-design.

1 and 2-designs have been examined in some detail and absolute bounds for the dimension of X, |X|, have been derived.^[8]

Bounds for unitary designs

Define ${\displaystyle \operatorname {Hom} (U(d),t,t)}$ as the set of functions homogeneous of degree t in ${\displaystyle U}$ and homogeneous of degree t in ${\displaystyle U^{*}}$, then if for every ${\displaystyle f\in \operatorname {Hom} (U(d),t,t)}$:

${\displaystyle {\frac {1}{|X|}}\sum _{U\in X}f(U)=\int _{U(d)}f(U)dU}$

then X is a unitary t-design.

We further define the inner product for functions ${\displaystyle f}$ and ${\displaystyle g}$ on ${\displaystyle U(d)}$ as the average value of ${\displaystyle {\bar {f}}g}$ as:

${\displaystyle \langle f,g\rangle$ :=\int _{U(d)}{\bar {f(U)}}g(U)dX}

and ${\displaystyle \langle f,g\rangle _{X}}$ as the average value of ${\displaystyle {\bar {f}}g}$ over any finite subset ${\displaystyle X\subset U(d)}$.

It follows that X is a unitary t-design if and only if ${\displaystyle \langle 1,f\rangle _{X}=\langle 1,f\rangle \quad \forall f}$.

From the above it is demonstrable that if X is a t-design then ${\displaystyle |X|\geq \dim(\operatorname {Hom} (U(d),\left\lceil {\tfrac {t}{2}}\right\rceil ,\left\lfloor {\tfrac {t}{2}}\right\rfloor ))}$ is an absolute bound for the design. This imposes an upper bound on the size of a unitary design. This bound is absolute meaning it depends only on the strength of the design or the degree of the code, and not the distances in the subset, X.^[9]

A unitary code is a finite subset of the unitary group in which a few inner product values occur between elements. Specifically, a unitary code is defined as a finite subset ${\displaystyle X\subset U(d)}$ if for all ${\displaystyle U\neq M}$ in X ${\displaystyle |\operatorname {tr} (U^{*}M)|^{2}}$ takes only distinct values.

It follows that ${\displaystyle |X|\leq \dim(\operatorname {Hom} (U(d),s,s))}$ and if U and M are orthogonal: ${\displaystyle |X|\leq \dim(\operatorname {Hom} (U(d),s,s-1))}$

See also

• Spherical design
• Equiangular lines
• Welch bounds

References

1. Dankert, Christoph; Cleve, Richard; Emerson, Joseph; Livine, Etera (2009-07-06). "Exact and approximate unitary 2-designs and their application to fidelity estimation". Physical Review A. 80 (1): 012304. arXiv:quant-ph/0606161. Bibcode:2009PhRvA..80a2304D. doi:10.1103/physreva.80.012304. ISSN 1050-2947. S2CID 46914367.
2. Hayashi, A.; Hashimoto, T.; Horibe, M. (2005-09-21). "Reexamination of optimal quantum state estimation of pure states". Physical Review A. 72 (3): 032325. arXiv:quant-ph/0410207. Bibcode:2005PhRvA..72c2325H. doi:10.1103/physreva.72.032325. ISSN 1050-2947. S2CID 115394183.
3. Emerson, Joseph; Alicki, Robert; Życzkowski, Karol (2005-09-21). "Scalable noise estimation with random unitary operators". Journal of Optics B: Quantum and Semiclassical Optics. 7 (10). IOP Publishing: S347–S352. arXiv:quant-ph/0503243. Bibcode:2005JOptB...7S.347E. doi:10.1088/1464-4266/7/10/021. ISSN 1464-4266. S2CID 17729419.
4. Hayden, Patrick; Preskill, John (2007-09-26). "Black holes as mirrors: quantum information in random subsystems". Journal of High Energy Physics. 2007 (9): 120. arXiv:0708.4025. Bibcode:2007JHEP...09..120H. doi:10.1088/1126-6708/2007/09/120. ISSN 1029-8479. S2CID 15261400.
5. Renes, Joseph M.; Blume-Kohout, Robin; Scott, A. J.; Caves, Carlton M. (June 2004). "Symmetric Informationally Complete Quantum Measurements". Journal of Mathematical Physics. 45 (6): 2171–2180. arXiv:quant-ph/0310075. Bibcode:2004JMP....45.2171R. doi:10.1063/1.1737053. hdl:10072/21107. ISSN 0022-2488. S2CID 17371881.
6. Ambainis, Andris; Emerson, Joseph (2007). "Quantum t-designs: T-wise independence in the quantum world". arXiv:quant-ph/0701126.
7. Collins, Benoît; Śniady, Piotr (2006-03-22). "Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group". Communications in Mathematical Physics. 264 (3). Springer Science and Business Media LLC: 773–795. arXiv:math-ph/0402073. Bibcode:2006CMaPh.264..773C. doi:10.1007/s00220-006-1554-3. ISSN 0010-3616. S2CID 16122807.
8. Gross, D.; Audenaert, K.; Eisert, J. (2007). "Evenly distributed unitaries: On the structure of unitary designs". Journal of Mathematical Physics. 48 (5): 052104. arXiv:quant-ph/0611002. Bibcode:2007JMP....48e2104G. doi:10.1063/1.2716992. ISSN 0022-2488. S2CID 119572194.
9. Aidan Roy; A. J. Scott (2009). "Unitary designs and codes". Designs, Codes and Cryptography. 53: 13–31. arXiv:0809.3813. doi:10.1007/s10623-009-9290-2. S2CID 19010867.