WorksMathematics
Orthogonal bases of symmetric unitary matrices in odd dimensions and the mixed-unitary rank of the symmetric Werner–Holevo channel
Abstract
Let Sym_n denote the space of complex symmetric n×n matrices with the Hilbert–Schmidt inner product. Girard, Leung, Levick, Li, Paulsen, Poon and Watrous showed that the symmetric Werner–Holevo channel on M_n has minimal mixed-unitary rank binom(n+1,2) if and only if Sym_n admits an orthogonal basis consisting of unitary matrices. They established this for even n and for n=3, and conjectured it for all odd n; Levick and Rahaman settled the case of primes n≡7 (mod 8). We introduce a family of symmetric unitaries (“chirped circulants”) for odd n and prove that, for this family, the pairwise orthogonality conditions reduce exactly to a square system of (n^2-1)/4 real equations in as many unknown phases. Using this reduction we give (i) a fully explicit basis for n=5, with all entries in an explicit degree-8 number field and an exact-arithmetic verification, and (ii) a computer-assisted proof, based on the Krawczyk operator evaluated in Arb ball arithmetic, that a symmetric unitary orthogonal basis exists for every odd n with 3≤n≤67. Consequently the conjecture of Girard et al. holds for all n≤68. We also record several obstructions to natural approaches for general odd n, and a further reduction for prime n.
Introduction
For a positive integer let , a complex vector space of dimension , equipped with the Hilbert–Schmidt inner product . The following question was asked on MathOverflow in 2018 [6]:
Does admit an orthogonal basis consisting of unitary matrices?
The question has a quantum-information interpretation. The symmetric Werner–Holevo channel [10] is
Its Choi rank is , and its mixed-unitary rank (the least number of unitaries in a decomposition ) is at least the Choi rank.
Theorem 1 [2 Theorem 19]. The channel on has mixed-unitary rank if and only if has an orthogonal basis consisting of unitary matrices.
(Theorem numbers for [2] refer to arXiv:2003.14405.) In [2] such bases are constructed for all even $n (Theorem 21 there) and for . For odd only the upper bound on the mixed-unitary rank is proved (Theorem 22 there). Based on numerical evidence, the authors conjecture that has minimal mixed-unitary rank for every . Numerical (nonrigorous) bases for odd up to 11 were also reported in [6].
Levick and Rahaman [5, Theorem 3.8, Corollary 3.12] (numbering as in arXiv:2105.00975) extended a construction of Bravyi and Smolin. Using real equiangular projections obtained from a construction of Calderbank, Hardin, Rains, Shor and Sloane [1], they settled the case of primes . Below 70 the odd values of covered by these results are . We did not find a rigorous treatment of any other odd in the literature.1
Results
For odd we introduce chirped circulants: matrices with a symmetric circulant unitary and . From of them and the diagonal “shifts” we obtain symmetric unitaries.
Reduction. We prove (Theorem 5) that these matrices are pairwise orthogonal if and only if explicit scalar quantities vanish. After fixing a gauge, this is a square real system with .
(Theorem 8). An explicit orthogonal basis of by symmetric unitaries. All entries lie in the number field . The proof is human-readable apart from two clearly marked polynomial identities. We also provide a complete exact-arithmetic verification.
(Theorem 10). For every odd the square system has a solution. The proof is computer-assisted: it applies the Krawczyk operator [4, 7, 8], evaluated rigorously in Arb midpoint–radius arithmetic [3], to an approximate solution.
Corollary 2. For every positive integer , the space has an orthogonal basis of unitary matrices. Equivalently, the symmetric Werner–Holevo channel on has mixed-unitary rank .
Proof. For the claim is trivial ( with basis ). For even this is [2 Theorem 21]; for odd it is Theorem 10. Apply Theorem 1. □
The case of general odd remains open; see § 5 for a conjecture, obstructions and a reduction for prime .
Chirped circulants and the reduction lemma
Throughout, is odd, and . Indices are taken in , , and denotes the inverse of 2 in . Let and for .
Definition 3. A vector is admissible if and for all . For admissible put
and let be the associated circulant. Given parameters and admissible , define
and
This gives matrices.
Lemma 4. Each is symmetric and unitary.
Proof. With we have , so is unitary. Since we get , so is symmetric. If is symmetric unitary and is diagonal unitary, then is symmetric unitary. Apply this twice. □
Theorem 5 (Reduction). For put
Then
and . Consequently the matrices are pairwise orthogonal if and only if for all . In that case , and is an orthogonal basis of consisting of symmetric unitaries.
Proof. By definition
Fix . Since is odd, is a bijection of . With we get , , , and . Hence
This proves the displayed formula. By Parseval, , so .
For : if the inner products vanish. Conversely, if for all , then the discrete Fourier transform of vanishes. Hence , and so .
Finally, pairwise orthogonal nonzero matrices form a basis. □
Remark 6 (Square system). Multiplying by a unimodular constant multiplies by a unimodular constant, so we may fix . Write with and . The unknowns are then . The conditions are real equations. We obtain a smooth map
whose zeros yield orthogonal bases of by symmetric unitaries.
Remark 7 (Unbiased-vector form). Set . Then . Hence the problem is equivalent to finding an orthonormal basis of the space of even functions on such that each , after removing the chirp , has a Fourier transform of constant modulus. Equivalently, is unbiased with respect to the “chirped Fourier basis” .
An explicit basis for
Let , , , and
All quantities below lie in , a field of degree 8 over . On , complex conjugation is the automorphism , . Put
and :
The minimal polynomial of over is . It is not monic, so is not a root of unity.
Let , let , and let be the all-ones matrix. Define
and for and .
These are chirped circulants with (in this section the seeds are indexed instead of ). Here with . The circulant equals with , i.e. .
Theorem 8. The 15 matrices are symmetric unitaries and satisfy . Hence they form an orthogonal basis of , and the symmetric Werner–Holevo channel on has mixed-unitary rank 15.
The theorem can be verified directly: the script verify_exact.py works in the ring using rational arithmetic only. It checks symmetry, for all 15 matrices, and all 120 Gram entries. The script verify_sympy.py is an independent check via Gröbner reduction (see § 6). The proof below explains the structure and isolates the two polynomial identities that we checked by computer.
Proof. Step 1 (). Note that and . Conjugating shows that implies , so the root set of is invariant under inversion in the unit circle.
One computes
Hence is a root of , and the two roots are distinct. Moreover and , so , i.e. .
Suppose a root had . Then the other root is , and , a contradiction. Thus , and are admissible.
Step 2 (). [Computer-checked identity] In one has and , hence . Thus is admissible, and by Lemma 4 all are symmetric unitaries.
Step 3 (reduction). By Theorem 5 it suffices to show . Here , with and for , and
Substituting in gives and , while ; hence .
[Computer-checked identity] Expanding with and and reducing modulo gives
Both numerators vanish by the definitions of and . □
Remark 9. Replacing by (the other root of ) gives a second basis; we checked this numerically. The two computer-checked identities are finite polynomial computations in . They are verified by verify_exact.py (the identity , together with ) and by reduce_eqs.py (the expansions of ).
Odd : a computer-assisted proof
Theorem 10. For every odd with and the choice (), the system of Remark 6 has a solution. Consequently has an orthogonal basis of symmetric unitary matrices.
Method
We use the following classical result [4, 7]; see also [8].
Krawczyk’s theorem. Let be a box, continuously differentiable, , and . Let be an interval matrix containing the Jacobian for every , and put
(evaluated in interval arithmetic). If , then has exactly one zero in .
For each we proceed as follows.
Approximate solution. Starting from random phases, a Levenberg–Marquardt least-squares solve followed by five Newton steps gives in IEEE double precision, with . The numbers are taken as exact binary rationals.
Box. with (rounded upward to Arb’s radius format; the same radius is used for ).
Rigorous enclosures. Using Arb [3] through python-flint 0.9.0 [9], at a working precision of 128 bits, we compute an enclosure of and an interval matrix enclosing :
the roots of unity and the phases are evaluated as rigorous complex balls;
the entries of are given by the explicit formulas
combined by the product rule in .
Preconditioner. is the floating-point inverse of , converted exactly to a ball matrix. Any real is admissible in the theorem.
Check. We evaluate in ball arithmetic and test componentwise. In every case (an upper bound computed in ball arithmetic) is at most , far inside the radius .
Results
Table 1 lists, for each odd : the dimension of the system; the bound on ; and the wall-clock time of certify.py n --from-center (excluding Python start-up and imports; almost all of it is the interval phase) on an 8-core Intel Xeon virtual machine (single-threaded). The last column indicates whether the case was covered by [2, 5] (“known”) or not (“new”; i.e. not covered by these papers and not found in our literature search). All 33 cases are certified, which proves Theorem 10.
| s | s | ||||||||
| 3 | 2 | 0.0 | known | 37 | 342 | 0.4 | new | ||
| 5 | 6 | 0.0 | new | 39 | 380 | 0.5 | new | ||
| 7 | 12 | 0.0 | known | 41 | 420 | 0.6 | new | ||
| 9 | 20 | 0.0 | new | 43 | 462 | 0.8 | new | ||
| 11 | 30 | 0.0 | new | 45 | 506 | 1.0 | new | ||
| 13 | 42 | 0.0 | new | 47 | 552 | 1.2 | known | ||
| 15 | 56 | 0.0 | new | 49 | 600 | 1.4 | new | ||
| 17 | 72 | 0.0 | new | 51 | 650 | 1.7 | new | ||
| 19 | 90 | 0.0 | new | 53 | 702 | 2.1 | new | ||
| 21 | 110 | 0.0 | new | 55 | 756 | 2.3 | new | ||
| 23 | 132 | 0.1 | known | 57 | 812 | 2.8 | new | ||
| 25 | 156 | 0.1 | new | 59 | 870 | 3.5 | new | ||
| 27 | 182 | 0.1 | new | 61 | 930 | 4.6 | new | ||
| 29 | 210 | 0.1 | new | 63 | 992 | 4.3 | new | ||
| 31 | 240 | 0.2 | known | 65 | 1056 | 4.9 | new | ||
| 33 | 272 | 0.2 | new | 67 | 1122 | 5.7 | new | ||
| 35 | 306 | 0.3 | new |
Table 1. Krawczyk certification, box radius , precision 128 bits. “” = (rigorous upper bound); “s” = seconds.
Proof of Theorem 10. For each in Table 1 the inclusion holds. By Krawczyk’s theorem has a (unique) zero . By Remark 6 and Theorem 5, the corresponding matrices form an orthogonal basis of by symmetric unitaries.
Consistency checks
These checks are not part of the proof.
The analytic Jacobian agrees with central finite differences to about , and the ball Jacobian agrees with the floating-point one to about (checked for ).
Negative control. Shifting the centre by , so that the true zero lies outside the box, makes the script report “not certified” (checked for ).
For every in Table 1, all matrices were also assembled in floating point directly from the archived centre (without using the formula for ). Their Gram matrix agrees with to , and symmetry and unitarity hold to .
The Jacobians at the solutions are well conditioned (e.g. for ).
Remarks, obstructions, and open problems
General odd
In every case we tried, a handful of random starting points sufficed to find a nondegenerate zero of . This suggests:
Conjecture 11. For every odd , the system (with ) has a nondegenerate real solution. In particular has an orthogonal basis of symmetric unitaries for every .
A natural approach would be a direct algebraic construction or a topological existence argument. We record several obstructions.
(1) Equal chirp parameters fail. Suppose all equal . Let , and take the orthonormal basis , () of the even functions. By Remark 7, for every . If were an orthonormal basis of the even functions, the matrix would be unitary. Its 0-th column would then have squared norm , a contradiction.
(2) Pure chirp spectra fail for prime . Suppose every with . If then , where is a quadratic Gauss sum with ; if then . Hence each is either a value or its conjugate (modulus or 1), or equals for some , of modulus or . In no case does vanish.
(3) Tensor products do not close the problem. Under one has , where denotes antisymmetric matrices. Since antisymmetric matrices of odd size are singular, contains no unitaries when is odd. So bases for odd do not directly yield one for .
(4) No degree argument. is -periodic in each variable, so it induces a map from the compact torus to . Such a map is never surjective, so its degree is 0: if 0 is a regular value, the zeros on counted with the sign of sum to 0. Hence existence of zeros cannot be obtained from a global degree count alone.
A further reduction for prime
For let . Since even functions are fixed by , depends only on the class of in , a group of order . In the notation of Remark 7:
Proposition 12. Let be an odd prime. Take the chirp parameters . Let with , and , where and has admissible spectrum. Then all are admissible for their chirp parameters. Moreover, the orthonormality conditions of Remark 7 reduce to
Proof. First, . The Fourier spectrum of is a permutation of that of , so it is again admissible. Next, corresponds to the circulant with spectrum and is -invariant. Hence
Up to gauge this is a square system with about real unknowns (namely and the phases of the spectrum of ). For we found nondegenerate numerical solutions; this is evidence, not proof. For and there are solutions (verified numerically to 60 significant digits; we have not written out an exact proof) in which the spectrum of is a single chirp off the origin, (), with free. For these have , and for we get . Numerically, this one-parameter family has no solutions for . A heuristic Weil-bound argument suggests that it fails for all large . Cose-t-wise (Gauss-period) generalizations of index 2 and 3 produced no solutions in our tests (). A proof for infinitely many primes along these lines would need a genuinely new explicit family.
Reproducibility
The ancillary files contain the following.
verify_exact.py: pure-Python exact verification of Theorem 8 (fractions only, about 1 s).verify_sympy.py: an independent Gröbner-basis verification (about 50 s).reduce_eqs.py: the expansions in Step 3.certify.py: the Krawczyk certification.python3 certify.py nsearches for a solution and certifies it.python3 certify.py n --from-centerre-certifies the archived centrecenters/cert_sol_nn.npy, which is exactly the centre used for Table 1.
logs/: the original logs and the run used for the table (recertify_from_centers.out).
The certification relies on the correctness of Arb’s ball arithmetic and of Krawczyk’s theorem. Floating-point computations are used only to produce the centre and the preconditioner , neither of which needs to be accurate for the validity of the proof.
Acknowledgements
The author used AI assistance in the literature search, in designing and running the computational experiments, in writing the accompanying verification and certification code, and in drafting the manuscript. The human author is solely responsible for verifying all results, for the correctness of the proofs and computations, and for the final text.
Tools used: Codex (OpenAI) and Claude (Anthropic), used as research and writing assistants. Specific version numbers were not recorded. AI is not listed as an author.
References
References
- [1]A. R. Calderbank, R. H. Hardin, E. M. Rains, P. W. Shor, and N. J. A. Sloane, A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Combin. 9 (1999), no. 2, 129–140.DOI
- [2]Mark Girard, Debbie Leung, Jeremy Levick, Chi-Kwong Li, Vern Paulsen, Xiu-Tung Wong, and John Watrous, On the mixed-unitary rank of quantum channels, Comm. Math. Phys. 394 (2022), no. 2, 919–951, arXiv:2003.14405.DOI
- [3]Fredrik Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput. 66 (2017), no. 8, 1281–1292.arxiv.org/abs/1611.02831
- [4]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), no. 3, 187–201.DOI
- [5]Jeremy Levick and Mizanur Rahaman, An extension of Bravyi–Smolin’s construction for UMEBs, Quantum Inf. Process. 20 (2021), no. 11, Paper No. 369, arXiv:2105.00975.DOI
- [6]Luftbahnfahrer, Existence of orthogonal basis of symmetric n × n matrices, where each matrix is unitary?, MathOverflow, question 316985, 2018, https://mathoverflow.net/questions/316985.
- [7]R. E. Moore, A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal. 14 (1977), no. 4, 611–615.DOI
- [8]Siegfried M. Rump, Verification methods: rigorous results using floating-point arithmetic, Acta Numer. 19 (2010), 287–449.
- [9]The FLINT team, python-flint: Python bindings for FLINT (incl. Arb), version 0.9.0, https://github.com/flintlib/python-flint, PyPI package python-flint.
- [10]R. F. Werner and A. S. Holevo, Counterexample to an additivity conjecture for output purity of quantum channels, J. Math. Phys. 43 (2002), no. 9, 4353–4357.DOI