Quantum Latin squares and unitary error bases

Introduction

We begin with the definition of a quantum Latin square.

A classical Latin square of order $n$ is an $n$-by-$n$ array of integers in the range $\{0,\ldots,n-1\}$, such that every row and column contains each number exactly once.

It is easy to see that the original array of numbers is a classical Latin square if and only if the corresponding grid of Hilbert space elements is a quantum Latin square. However, as Example 2 makes clear, not every quantum Latin square is of this form.

Our main results are on the construction of unitary error bases (UEBs) , also known as unitary operator bases. These are basic structures in quantum information which play a central role in quantum teleportation , dense coding and error correction . Since UEBs are hard to find, and given their wide applicability, construction techniques for UEBs have been widely studied . In this paper, we propose a new method for construction of UEBs:

Quantum shift-and-multiply method (QSM). Requires a quantum Latin square and a family of Hadamard matrices. (See Definition 18.)

We compare this to the other methods that have been proposed in the literature:

Shift-and-multiply method (SM). Requires a classical Latin square and a family of Hadamard matrices. (See Definition 21.)

Hadamard method (HAD). Requires a pair of mutually-unbiased bases. (See Definition 33.)

Algebraic method (ALG). Requires a finite group equipped with a projective representation, satisfying certain properties. (See Definition 41.)

Our theorems concern the relationships between these constructions. In Theorems 22 and 34, we prove that QSM contains SM and HAD as special cases. We also use QSM to construct a concrete unitary error basis $\mathcal{M}$ (Example 19), and prove that it is not equivalent to one arising from SM, HAD or ALG (Corollaries 32, 39 and 44 respectively.)

The relationships between these constructions, up to a standard notion of equivalence of UEBs (see Definition 16), are indicated by the following Venn diagram:

Our work strongly extends previous results, in an area that has not seen progress since 2003. But there is much still to be settled: in particular, we do not know whether ALG is a subset of QSM, or whether QSM equals UEB.

Categorical quantum mechanics is a research programme in which powerful techniques of monoidal category theory are used to understand quantum computational phenomena , using a graphical notation which can make the high-level structure of computations easier to understand. The main results of this paper were originally developed using this approach (see also ), although we have chosen to present them here in a conventional way. We feel this is a good advert for the power of categorical quantum mechanics; certainly, we could not have developed our results without using these techniques.

There are interesting connections between Hadamard matrices, unitary error bases and quantum Latin squares. In Section 2 we show that a quantum Latin square can be constructed from any Hadamard matrix. Hadamard matrices are mathematically equivalent to the data for a pair of mutually unbiased bases , the study and classification of which is a major activity in quantum computer science . It has also been shown that in some cases a family of mutually unbiased bases can be extracted from a UEB . So quantum Latin squares can be built from Hadamards, which can be built from UEBs, which can be built from quantum Latin squares; an interesting tapestry of results for which we currently lack a good intuition.

Acknowledgements. The authors are grateful to Dominic Verdon for useful discussions, and to EPSRC for financial support.

Quantum Latin squares from Hadamard matrices

In this section we introduce some basic properties of quantum Latin squares, show how to construct a quantum Latin square from a Hadamard matrix, and prove that our quantum Latin square of Example 2 is not equivalent to one arising in this way.

We begin by developing a precise notation for working with quantum Latin squares. Throughout, we assume we are working with a quantum Latin square of order $n$, and that indices $i,j,k,p,q$ range from to $n-1$.

For a quantum Latin square $Q$, we define the following:

$Q_{i}$ is the matrix whose columns are the entries of the $i$th row of $Q$;

For a matrix $M$, it is a standard notation to write $M_{ij}$ for the element at the $i$th row and $j$th column. Combining this with Definition 4, we have the following:

Note that the order of the final two indices changes.

The condition (5) equivalently says that the matrices formed by the columns of the Latin square are unitary, but this is not a fact that we will need directly.

There are certain trivial ways to transform a quantum Latin square into a different quantum Latin square, which we use to define a notion of equivalence.

Two quantum Latin squares are equivalent when one can be obtained from the other by permuting rows and columns, multiplying rows and columns by unit complex numbers, and applying a fixed unitary to every element. Algebraically, quantum Latin squares $Q$ and $Q^{\prime}$ are equivalent when there exists some unitary $U$, diagonal unitary $D$, permutation matrix $P$, permutation $\phi$, and a family of unit complex numbers $c_{j}$, such that the following holds:

We now give the standard definition of a Hadamard matrix, as a square matrix with entries of absolute value 1 which is proportional to a unitary matrix.

A Hadamard matrix of order n is an $n$-by-$n$ matrix $H$ with the following properties for all $i,j$, which we write in both matrix and index form:

Two Hadamard matrices are equivalent when one can be obtained from the other by permuting rows and columns, and multiplying rows and columns by unit complex numbers. Algebraically, $H,H^{\prime}$ are equivalent if there exist $P_{1},P_{2}$ permutation matrices and $D_{1},D_{2}$ unitary diagonal matrices such that:

We now give the construction of a quantum Latin square from a Hadamard matrix.

For a Hadamard matrix $H$ of order $n$, its associated quantum Latin square $Q_{H}$ of order $n$ is defined as follows:

We will refer to a quantum Latin square constructed in this way as a Hadamard quantum Latin square.

The associated quantum Latin square construction is correct.

To establish property (4), we note that $(Q_{H})_{j}$ is the composite of three unitary matrices, and is therefore unitary. To verify (5), we write expression (12) in index form:

In the second equality here, the sum is being reorganized. ∎

We now establish a lemma which we will use to prove Lemma 13 and later Proposition 36.

Let $p$ be the permutation associated with the permutation matrix $P$ such that $P=\sum_{k}|p(k)\rangle\langle k|$ and $D$ be a diagonal unitary. Then the following equations hold:

Equivalent Hadamards give rise to equivalent quantum Latin squares.

We will prove equivalence on a case-by-case basis. Suppose $H^{\prime}=P\circ H$. Then we have the following, where we use the fact that $P^{-1}=P^{\dagger}=P^{T}$:

Finally, we prove that our example quantum Latin square does not arise in this way, even up to equivalence. This makes use of some results that we prove later in the paper.

The quantum Latin square given in Example 2 is not equivalent to a quantum Latin square constructed from a Hadamard.

For a contradiction, suppose that $Q$ and $Q_{H_{\alpha}}$ are equivalent in the manner of Definition 6, for some fixed value of $\alpha$. So there exists some unitary matrix $U$, diagonal unitary matrix $D$, permutation matrix $P$, permutation $\phi$, and a family of unit complex numbers $c_{j}$, such that the following holds:

Note that the composite $P\circ D$ is unitary; so the families of matrices $(Q_{H_{\alpha}})_{j}$ and $Q_{j}$, which are unitary by Lemma 5, are equivalent families in the sense of Definition 16.

The family $(Q_{H_{\alpha}})_{j}$ are simultaneously monomializable, by the matrix $Y$ defined in equation (33). (This follows from Theorem 38, in which we show that the members of $\mathcal{F}_{\alpha}$, which include the $(Q_{H_{\alpha}})_{j}$ as a subset, are simultaneously monomializable.) So all together, the family of matrices $Q_{j}$ contains the identity, and is equivalent in the sense of Definition 16 to a monomial family. So by Proposition 28, the family $Q_{j}$ is simultaneously monomializable, and thus by Proposition 29, their 12th powers must all commute. But as established in the proof of Theorem 30, the 12th powers of $Q_{1}=\mathcal{M}_{01}$ and $Q_{2}=\mathcal{M}_{02}$ do not commute. This gives us our contradiction.∎

Unitary error bases from quantum Latin squares

In this section we define unitary error bases, and present our new quantum shift-and-multiply construction, which produces a unitary error basis from a quantum Latin square equipped with a family of Hadamard matrices. We then introduce an example UEB $\mathcal{M}$, which will play an important role in later sections where we show that it cannot arise from the shift-and-multiply, Hadamard or algebraic methods, even up to equivalence.

We begin with the definition of unitary error basis. As remarked in the introduction, these structures play a central role in quantum computation.

For a Hilbert space $H$ of dimension $n$, a unitary error basis (or unitary operator basis) is a family of $n^{2}$ unitary matrices $U_{ij}:H\to H$ which form an orthogonal basis:

There is a standard notion of equivalence of unitary error bases, which we recall here.

Two families of unitary matrices $\mathcal{A}$, $\mathcal{B}$ are equivalent if there are unitary matrices $U$ and $V$, such that for any element $A\in\mathcal{A}$, there is an element $B\in\mathcal{B}$ and a unit complex number $c$ such that the following holds:

The following technical lemma will be useful later.

Let $D$ be a diagonal matrix, and $A$ be a square matrix which is zero along the main diagonal, such that $D$ and $A$ are composable. Then $D\circ A$ is zero along the main diagonal.

We perform the following calculation of the diagonal elements of $D\circ A$:

Here we apply the definition of matrix composition, the diagonal property of $D$, the properties of the sum, and the hypothesis that $A$ is zero along the main diagonal. ∎

We now define the main construction of focus in this paper. This construction is similar to Werner’s shift-and-multiply method , the difference being that ours is in terms of quantum Latin squares. As usual, we take all indices in the range to $n-1$.

Let $Q$ be a quantum Latin square of order $n$, and $H_{j}$ be a family of $n$ Hadamard matrices of order $n$. Then the associated quantum shift-and-multiply basis has the following elements:

In words, the $(i,j)$ entry of the quantum shift-and-multiply basis is the matrix given by the $j$th row of the quantum Latin square, composed with the diagonal matrix formed from the $i$th row of the $j$th Hadamard matrix.

We illustrate this with an example. This example will play a central role, as we will show in the remainder of the paper that it cannot be obtained, even up to equivalence, by any of the existing methods of unitary error basis construction.

The quantum shift-and-multiply basis $\mathcal{M}$ is constructed from the quantum Latin square of Example 2, and from the following family of Hadamard matrices:

The resulting family of 16 matrices is listed in Appendix A.1.

We now show that quantum shift-and-multiply bases are unitary error bases. This has similarities with Werner’s original proof for standard shift-and-multiply bases (see Section 4), but our use of quantum Latin squares requires nontrivial extra ideas.

Quantum shift-and-multiply bases are unitary error bases.

We must establish the following trace property:

Next we consider the case that $j=j^{\prime}$ and $i\neq i^{\prime}$. We perform the following calculation:

The final expression is equal to the inner product of rows $i$ and $i^{\prime}$ of the Hadamard $H_{j}$. Since distinct rows of a Hadamard are orthogonal, the result is zero as required.

It remains to consider the case that $j\neq j^{\prime}$. We use the cyclic property of the trace to rearrange our trace expression:

Hence by Lemma 17, expression (25) is zero as required. ∎

Shift-and-multiply method

The shift-and-multiply method of Werner , which was a direct inspiration for our own results, can straightforwardly be seen as a special case of our quantum shift-and-multiply method. Our focus in this section is the proof that the unitary error basis $\mathcal{M}$ of Example 19 is not equivalent to a shift-and-multiply basis, and thus that the shift-and-multiply bases are strictly contained within the quantum shift-and-multiply bases.

A shift-and-multiply basis is a quantum shift-and-multiply basis where the quantum Latin square is a classical Latin square.

Every shift-and-multiply basis is a quantum shift-and-multiply basis.

Follows immediately from Definitions 3 and 21. ∎

Monomial matrices will be crucial to our proof strategy.

A monomial matrix is a square matrix with exactly one nonzero entry in each row and each column. Equivalently, it is any matrix $A$ which can be expressed as $A=D_{A}\circ P_{A}$, where $D_{A}$ is a diagonal matrix and $P_{A}$ is a permutation matrix.

Let $p$ be a permutation, $P=\sum_{k}|p(k)\rangle\langle k|$ be the corresponding permutation matrix, and $D=\sum_{k}d_{k}|k\rangle\langle k|$ and $D^{\prime}=\sum_{k}d_{p(k)}|k\rangle\langle k|$ be diagonal matrices. Then the following holds:

The set of monomial matrices is closed under composition, taking inverses, taking adjoints, and multiplication by nonzero complex scalars.

A square matrix $A$ is monomializable if there exists a unitary matrix $U$ such that $U\circ A\circ U^{\dagger}$ is monomial.

A family of square matrices $A_{1},...,A_{n}$ are simultaneously monomializable if they are all monomializable by the same unitary matrix $U$.

We establish the following propositions, the first of which is adapted and generalized to suit our purposes from the literature.

If a family $\mathcal{S}$ of unitary matrices containing the identity is equivalent (in the sense of Definition 16) to a family of monomial matrices, then the members of $\mathcal{S}$ are simultaneously monomializable.

The left hand side is monomial by Lemma 25, and hence $U$ simultaneously monomializes $S_{i}$. ∎

Let $A,B$ be square matrices of size $n$, and let $\mu_{n}$ be the lowest common multiple of $\{1,2,...,n\}$. If $A$ and $B$ are simultaneously monomializable, then $A^{\mu_{n}}$ and $B^{\mu_{n}}$ commute.

Suppose $A,B$ are simultaneously monomializable, with $\mu_{n}$ defined as above. Then there exists a unitary matrix $U$ such that $UAU^{\dagger}=D_{A}P_{A}$ and $UBU^{\dagger}=D_{B}P_{B}$ where $D_{A},D_{B}$ are diagonal matrices and $P_{A},P_{B}$ are permutation matrices. Note that $A=U^{\dagger}D_{A}P_{A}U$, so we have the following:

The central equality here holds because diagonal matrices commute. ∎

We are now ready to prove the necessary properties of our example basis.

The basis $\mathcal{M}$ of Example 19 is not equivalent to a monomial basis.

For a contradiction, suppose that $\mathcal{M}$ is equivalent to a monomial basis. Note that $\mathcal{M}$ contains the identity matrix, so by Proposition 28 the elements of the UEB are simultaneously monomializable. The least common multiple of $\{1,2,3,4\}$ is $\mu_{4}=12$; thus by Proposition 29 the 12th powers of the elements of $\mathcal{M}$ will commute. To exhibit the contradiction, we compute the following commutator:

Shift-and-multiply bases are monomial bases.

Recall from Definition 21 of a shift-and-multiply basis that each matrix is the product of a diagonal matrix with the permutation matrix given by a row of a classical Latin square. By definition, the result is a monomial matrix. ∎

The basis $\mathcal{M}$ of Example 19 is not equivalent to a shift-and-multiply basis.

Immediate from Theorem 30 and Proposition 31. ∎

Hadamard method

In this section we study the Hadamard method, a direct construction of a unitary error basis from a Hadamard matrix. While this is certainly known, we cannot find a clear description of it in full generality, although a special case is worked out in detail in . The main results of this section are Theorem 34, where we show that the quantum shift-and-multiply method contains the Hadamard method as a special case, and Corollary 39, in which we show that this containment is proper.

For a Hadamard matrix $H$ of order $n$, its associated Hadamard basis $\{(U_{H})_{ij}\}$ is defined as follows:

A Hadamard basis is a quantum shift-and-multiply basis.

A Hadamard basis is a unitary error basis.

If two Hadamard matrices are equivalent by Definition 8, then their associated unitary error bases are equivalent by Definition 16.

We will once again prove equivalence on a case-by-case basis. Again suppose $H^{\prime}=P\circ H$. Then we have the following:

The case $H^{\prime}=H\circ D$ is similar. ∎

Write $\mathcal{F}_{\alpha}$ for the unitary error basis arising from $H_{\alpha}$ by the Hadamard method, for some fixed $\alpha\in[0,\frac{\pi}{2}]$. By Propositions 36 and 37 all unitary error bases arising from Hadamards in dimension $4$ are equivalent to $\mathcal{F}_{\alpha}$, for some value of $\alpha$. But the following unitary matrix simultaneously monomializes $\mathcal{F}_{\alpha}$, for all values of $\alpha$:

The basis $\mathcal{F_{\alpha}^{\prime}}=\{Y\circ F_{ij}\circ Y^{\dagger}|F_{ij}\in\mathcal{F}\}$ is listed in Section A.2, and is monomial and equivalent to $\mathcal{F}_{\alpha}$. This completes the proof. ∎

The basis $\mathcal{M}$ of Example 19 is not equivalent to a Hadamard basis.

Algebraic method

Another technique for constructing UEBs is the algebraic method, due to Knill . UEBs obtained using this technique are called nice error bases. The main result in this section is Corollary 44, that the basis $\mathcal{M}$ of Example 19 is not equivalent to a nice error basis. Throughout this section, we use ‘$\propto$’ to denote equality up to multiplication by a unit complex number.

The following result will also be useful.

Given a unitary projective representation $\rho$ of a group $G$, the following holds:

As follows: $\!\rho(g)^{\dagger}=\rho(g)^{\dagger}\rho(1)=\rho(g)^{\dagger}\rho(gg^{-1})\stackrel{{\scriptstyle\makebox[0.0pt]{\smash{\tiny\eqref{eq:ghprop}}}}}{{\propto}}\rho(g)^{\dagger}\rho(g)\rho(g^{-1})=\rho(g^{-1})$. ∎

We now give the definition of a nice error basis, and show that a nice error basis is a unitary error basis.

Let $G$ be a finite group of order $n^{2}$, and let $\rho$ be an $n$-dimensional unitary projective representation of $G$, such that for all $g\in G$ not equal to the identity, we have the following:

Then a nice error basis $\mathcal{R}_{G,\rho}:=\{\rho(g)\,|\,g\in G\}$ is the image of $\rho$.

A nice error basis is a unitary error basis.

We now prove a key proposition, which we will use to establish that our example basis $\mathcal{M}$ of Example 19 is not equivalent to a nice error basis.

We now perform the following calculation, for any $g\in G$:

So $\mathcal{S}$ is closed under adjoints, up to multiplication by a unit complex number. ∎

The basis $\mathcal{M}$ of Example 19 is not equivalent to a nice error basis.

By inspection of the elements of $\mathcal{M}$, as listed in Section A.1. For a contradiction, let us assume that $\mathcal{M}$ is equivalent to a nice error basis. Note that $\mathcal{M}$ contains the identity matrix; then by Proposition 43, it must be closed under taking adjoints, up to a unit complex number. But this is clearly false: for example, the second element of the first row of $\mathcal{M}_{01}$ has absolute value $\frac{1}{\sqrt{5}}$, but no member of $\mathcal{M}$ has an element with the same absolute value in the second element of the first column. ∎

References

Appendix A Lists of unitary error bases

Here we list the unitary error bases that we make use of in the main text.

Here we list the unitary error basis $\mathcal{M}$ defined in Example 19.

Here we list the unitary error basis $\mathcal{F^{\prime}}$ defined in the proof of Theorem 38.