Zauner’s conjecture is true in dimension 17

Congrats to Tuan-Yow Chien for proving Zauner’s conjecture in dimension 17! The proof appears in his PhD thesis, which was written under the advice of Shayne Waldron. Recall that Zauner’s conjecture claims that SIC-POVMs (i.e., collections of d^2 equiangular lines in \mathbb{C}^d) exist for every dimension d. To date, SIC-POVMs are only known to exist in a few dimensions, and a recent numerical study suggests that they exist whenever d\leq 67. At some level, I’m surprised that an infinite family of SIC-POVMs has yet to emerge despite the apparent wide-spread interest in the problem (for example, see these statements of interest by Scott Aaronson and Peter Shor).

I find Tuan-Yow’s solution to be particularly interesting because of the techniques he uses. In particular, he first looks to this paper for the numerical approximation of a suspected SIC-POVM in dimension 17. We note that these SIC-POVMs are generated by taking the orbit of some vector (called the fiducial vector) under the Heisenberg-Weyl group. He increases the precision of this approximation by using it to initialize an iterative procedure that one might suspect converges to a SIC-POVM. After obtaining 2000 digits of precision, he then considers the projection operator onto the span of the numerical fiducial vector and decomposes it in terms of a certain basis of operators (namely, d^2 orthogonal members of the Heisenberg-Weyl group). Call the coefficients in this basis the overlaps.

At this point, he leverages certain conjectures regarding the field structure of the entries of the fiducial vector. In particular, for a certain field extension of \mathbb{Q} that contains the entries of the fiducial vector, the corresponding Galois group is conjectured to permute the overlaps. As such, one may apply the Galois group to the numerical overlaps and identify the orbits. Tuan-Yow then produces various polynomials from the orbits, whose coefficients are conjectured to lie in \mathbb{Q}(a), where a is the square root of the square-free part of (d-3)(d-1). This is the point at which the numerical approximation is converted to an analytic expression. In particular, the coefficients are necessarily \mathbb{Q}-linear combinations of 1 and a, and you need a lot of precision to make good guesses for the scalar multiples. The exact fiducial vector is then determined by finding the roots of these polynomials.

The fact that this method even works is substantial evidence in favor of the underlying conjectures. Also, this method presumably works for higher dimensions, but as Tuan-Yow points out in his thesis, it is particularly painful to factor the polynomial from a computational perspective, and he expects this to be a barrier for tackling higher-dimensional SIC-POVMs.

An analytic expression for the fiducial vector is provided in Appendix C, and I literally laughed out loud when I saw that it took over 40 pages to contain the expression. It’s certainly believable that computation is a bottleneck when the length of the output is so large. On a whim, I decided to compare with the expressions for other known SIC-POVMs, which are provided on Zauner’s webpage. For the sake of illustration, I counted the number of characters in each of these expressions and plotted the results:

fiduciallengths

(Observe the log scale on the vertical axis.) The blue and red points denote the known constructions, whereas yellow denotes Tuan-Yow’s new construction. I decided use red to highlight the points corresponding to constructions that were discovered by leveraging certain dimension-specific symmetries, thereby decreasing their description lengths (dimensions 7 and 19 are covered by this paper; 24, 35 and 48 by this paper; and 8, 12, and 28 by this paper). For the remaining points (in blue), I fit an exponential curve.

From the data, it appears that an underlying bottleneck with Zauner’s conjecture is description length. In fact, suppose for the moment that SIC-POVMs exist for every dimension, and consider the dream solution to Zauner’s conjecture: an algorithm that on input d produces a fiducial vector whose orbit under the Heisenberg-Weyl group is a SIC-POVM. Considering the above data, I’m willing to believe that such an algorithm necessarily takes exponential time in d just to write the output (at least in the worst case). If true, this doesn’t rule out the existence of an infinite family of SIC-POVMs for which the algorithm takes polynomial time in d (meaning the description length doesn’t grow so rapidly), and I’m hopeful that such a family exists.

Advertisements

2 thoughts on “Zauner’s conjecture is true in dimension 17

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s