# Given two basis sets for a finite Hilbert space, does an unbiased vector exist?

Let $\{A_n\}$ and $\{B_n\}$ be two bases for an $N$-dimensional Hilbert space. Does there exist a unit vector $V$ such that:

$$(V\cdot A_j)\;(A_j\cdot V) = (V\cdot B_j)\;(B_j\cdot V) = 1/N\;\;\; \ \text{for all} \ 1\le j\le N?$$

Notes and application:
That the $\{A_n\}$ and $\{B_n\}$ are bases means that
$$(A_j\cdot A_k) =\left\{\begin{array}{cl} 1&\;\text{if }j=k,\\ 0&\;\text{otherwise}.\end{array}\right.$$

In the physics notation, one might write $V\cdot A_j = \langle V\,|\,A_j\rangle$. In quantum mechanics, $P_{jk} = |\langle A_j|B_k\rangle|^2$ is the "transition probability" between the states $A_j$ and $B_k$. "Unbiased" means that there is no preference in the transition probabilities. A subject much studied in quantum information theory is "mutually unbiased bases" or MUBs. Two mutually unbiased bases satisfy
$|\langle A_j|B_k\rangle|^2 = 1/N\;\;$ for all $j,k$.

If it is true that the vector $V$ always exists, then one can multiply the rows and columns of any unitary matrix by complex phases so as to obtain a unitary matrix where each row and column individually sums to one.

If true, then $U(n)$ can be written as follows:
$$U(n) = \exp(i\alpha) \begin{pmatrix}1&0&0&0...\\0&e^{i\beta_1}&0&0...\\0&0&e^{i\beta_2}&0...\end{pmatrix} M \begin{pmatrix}1&0&0&0...\\0&e^{i\gamma_1}&0&0...\\0&0&e^{i\gamma_2}&0...\end{pmatrix}$$ where the Greek letters give complex phases and where $M$ is a "magic" unitary matrix, that is, $M$ has all rows and columns individually sum to 1.

And $M$ can be written as $M=\exp(im)$ where $m$ is Hermitian and has all rows and columns sum to 0. What's significant about this is that the $m$ form a Lie algebra. Thus unitary matrices can be thought of as complex phases, plus a Lie algebra. This is a new decomposition of unitary matrices.

Since $m$ is Hermitian and has all rows and columns sum to 0, it is equivalent to an $(n-1)\times(n-1)$ Hermitian matrix with no restriction on the row and column sums. And this shows that $U(n)$ is equivalent to complex phases added to an object (the $M$ matrices) that is equivalent to $U(n-1)$. This gives a recursive definition of unitary matrices entirely in terms of complex phases.

-
I think if they are orthonormal bases, then they can me mutually unbiased (i.e all the vectors in the first basis are unbiased with respect to the other). –  PEV Mar 22 '11 at 3:20
By bases, I did mean orthonormal. And it's well known that it's always possible to choose at least three bases which are pair-wise mutually unbiased. This fact is mentioned in passing in this review article: arxiv.org/abs/quant-ph/0610216 –  Carl Brannen Mar 22 '11 at 3:44
@Carl, by $N$-dimensional Hilbert space you actually mean complex Hilbert space? If so the problem can be restated in terms of elements of $\mathbb{C}^N$, where $\mathbb{C}$ is space of complex numbers. So stated this problem looks like a problem of finding equiangular vector. For $\mathbb{R}^N$ this comes up in least angle regression so this question and answer might be of interest. I looked at the original Effron paper mentioned there and for ... –  mpiktas Mar 22 '11 at 11:52
... real spaces $\mathbb{R}^N$ the answer seems no. Since I do not have conclusive proof of that I am not posting this as an answer. –  mpiktas Mar 22 '11 at 11:53
@mpiktas; Yes, complex Hilbert space. There's some partial results and computer studies, eventually I'll post those as incomplete answers. But I'm hoping that someone will recognize the problem as trivial when looked at through some mathematical prism. –  Carl Brannen Mar 22 '11 at 20:54

## 4 Answers

I believe the answer to be yes, and it follows by some symplectic geometry of Lagrangian intersections.

Let $U$ be the unitary matrix so that $B_j = U A_j$. Without loss of generality, we will also assume that $A_j = e_j$. This means that $B_j = U e_j$.

We will identify $\mathbb C^N = \mathbb R^{2N}$.

Then, the first condition on the vector $V$ is that: $$|(V, e_j)|^2 = \frac{1}{N}, j=1, \dots, N$$ This is equivalent to saying that $V = \frac{1}{\sqrt{N}} \sum \mathrm e^{i \theta_j} e_j$, or, in other words, that $V$ lies in the Lagrangian torus in $\mathbb R^{2N}$ with the standard symplectic structure $\sum dx_j \wedge dy_j$, defined by $\{ |x_j|^2 + |y_j|^2 = \frac{1}{\sqrt{N}} \}$.

The second condition on $V$ is that $$|(V, U e_j)|^2 = \frac{1}{N}.$$ Thus, $U^* V$ also should lie in the torus $L$. Thus, the vector $V$ exists if and only if $L \cap UL$ is non-empty.

(Note the first condition gives automatically that $V$ is a unit vector.)

Right now, I don't see how to take advantage of the linearity in this problem, so I will use an incredibly high powered theory (Floer theory). If I think of a better solution, I will update.

Notice that the action of $U$ on $\mathbb C^N$ induces a map on $\mathbb CP^{N-1}$. Furthermore, if we write $U=\mathrm{e}^{iH}$ for a Hermitian $H$, then $U$ is the time-1 map of the Hamiltonian flow generated by the Hamiltonian $$h(v) = \frac{1}{2} \Re (v, Hv).$$

Finally, we note that $L$ projects to the Clifford torus $L'$ in $\mathbb CP^{N-1}$. It is known for Floer theoretic reasons (not sure who first proved it... there are now many proofs in the literature) that the Clifford torus is not Hamiltonian displaceable, so there must always exist an intersection point. After normalizing, this lifts to an intersection point in $\mathbb C^N$, as desired.

Note that the Floer homology argument is a very powerful tool. I suspect that a much simpler proof can be found, since this doesn't use the linear structure.

EDIT: Apparently my use of the term "Clifford torus" is non-standard. Here is what I mean by it: Consider $\mathbb CP^{N-1}$ as the quotient of the unit sphere in $\mathbb C^{N}$ by the $S^1$ action by multiplication by a unit complex number (as we have defined here). In the unit sphere there is a real $N$ dimensional torus given by $|z_1| = |z_2| = \dots = |z_N| = \frac{1}{\sqrt{N}}$. The image of this $N$ dimensional torus by the quotient map is an $N-1$ dimensional torus in $\mathbb CP^{N-1}$. Equivalently, it is the torus given in homogeneous coordinates on $\mathbb CP^{N-1}$ by $[e^{i \theta_1}, e^{i \theta_2}, \dots, e^{i \theta_{N-1}}, 1]$.

-
What is $P^{N-1}$? Also by $U^{*}$ you denote conjugate transpose of $U$? Very interesting answer, did not even think that this question can generate answers from this field. –  mpiktas Mar 30 '11 at 7:00
@mpiktas: $\mathbb{C}P^{N−1}$ is the projective space obtained by identifying rays in $\mathbb{C}^N$. –  joriki Mar 30 '11 at 7:08
@mpiktas, yes, I mean the conjugate transpose by $U^*$. Sorry if it is a non-standard notation. As joriki said, $\mathbb CP^{N-1}$ is the quotient of $\C^N \setminus \{ 0 \}$ by the relation that $v \sim \lambda v$ for $\lambda \in \mathbb C$. This is equivalent to taking a constant radius sphere in $\mathbb C^N$, and taking the quotient by the relation $v \sim \mathrm{e}^{i t} v$. Given that the sphere is a level set of $h$, and on this level set, $h$ is equivariant, is what allows us to say that it descends to $\mathbb CP^{N-1}$. –  Sam Lisi Mar 30 '11 at 11:51
@Sam Lisi, I rarely encounter conjugate transposes in my daily work, so I do not know :) The only usage of star I know (now knew) is for convolution, hence need for clarification. –  mpiktas Mar 30 '11 at 13:05
@Carl Brannen, I believe the result is first established by Cho, arxiv.org/abs/math.SG/0308224, but it may be older. I am more familiar with the proof in the work of Biran-Cornea. (eg. math.SG/0808.3989 and math.SG/0808.2440). (They prove the Clifford torus is "wide" by their definition of "wide", and a displaceable Lagrangian is never "wide".) The result also can be deduced from work of Oh, Cho and Oh (math.SG/0308225) and a different formulation due to Polterovich & Entov (0410338v2). Also, Fukaya-Oh-Ohta-Ono (1011.4044v1). –  Sam Lisi Apr 6 '11 at 15:58

This is not a full answer, but I don't intend to work on this in the next two weeks ;-), so I thought I'd put it up here and perhaps someone else can complete it.

Writing $U_{jk}=\langle A_j\mid B_k\rangle$ (with $U$ unitary), we can formulate the problem like this: $V$ must have a component of length $1/\sqrt{N}$ along each $B_k$, so we can write it as

$$V=\frac{1}{\sqrt{N}}\sum_k\mathrm{e}^{\mathrm{i}\phi_k}B_k\;.$$

Then the condition that the projections onto the $A_j$ also all have length $1/\sqrt{N}$ becomes

$$\sqrt{N}\langle A_j \mid V\rangle=\sum_k\langle A_j\mid\mathrm{e}^{\mathrm{i}\phi_k} B_k\rangle=\sum_k U_{jk}\mathrm{e}^{\mathrm{i}\phi_k}=\mathrm{e}^{\mathrm{i}\theta_j}\;.$$

To manipulate this more easily, we can introduce diagonal matrices $\Phi$ and $\Theta$ with diagonal elements $\phi_k$ and $\theta_j$, respectively. Then the condition becomes

$$U\mathrm{e}^{\mathrm{i}\Phi}\vec{1}=\mathrm{e}^{\mathrm{i}\Theta}\vec{1}\;,$$

where $\vec{1}$ is the vector with all components $1$.

Now all unitary matrices $U$ can be written as $U=\mathrm{e}^{\mathrm{i}H}$ with $H$ Hermitian, and conversely every such exponential is a unitary matrix. Thus, we can always find a vector $V$ for any unitary $U$ if and only if we can always find $V$ for any Hermitian $H$. In particular, we can consider the one-dimensional family of unitary matrices $\mathrm{e}^{\mathrm{i}\lambda H}$ with Hermitian matrix $H$ and real number $\lambda$, and our problem then becomes showing that for arbitrary $H$ we can find $V$ for all $\lambda$. In this way we can consider the path from the identity, where we know that $V$ exists, to an arbitrary unitary matrix $\mathrm{e}^{\mathrm{i}\lambda H}$ and reduce the problem to a differential equation along this path. Thus, letting $\Phi$ and $\Theta$ (but not $H$) depend on $\lambda$, we get

$$\mathrm{e}^{\mathrm{i}\lambda H} \mathrm{e}^{\mathrm{i}\Phi(\lambda)}\vec{1}= \mathrm{e}^{\mathrm{i}\Theta(\lambda)}\vec{1}\;,$$

and differentiating with respect to $\lambda$ yields

$$H\mathrm{e}^{\mathrm{i}\lambda H} \mathrm{e}^{\mathrm{i}\Phi}\vec{1}+ \mathrm{e}^{\mathrm{i}\lambda H}\mathrm{e}^{\mathrm{i}\Phi}\Phi'\vec{1} = \mathrm{e}^{\mathrm{i}\Theta}\Theta'\vec{1}\;,$$

$$\mathrm{e}^{-\mathrm{i}\Theta}H\mathrm{e}^{\mathrm{i}\lambda H} \mathrm{e}^{\mathrm{i}\Phi}\vec{1}+ \mathrm{e}^{-\mathrm{i}\Theta}\mathrm{e}^{\mathrm{i}\lambda H}\mathrm{e}^{\mathrm{i}\Phi}\Phi'\vec{1} = \Theta'\vec{1}\;,$$

$$\mathrm{e}^{-\mathrm{i}\Theta}H \mathrm{e}^{\mathrm{i}\Theta}\vec{1}+ \mathrm{e}^{-\mathrm{i}\Theta}\mathrm{e}^{\mathrm{i}\lambda H}\mathrm{e}^{\mathrm{i}\Phi}\vec{\Phi}' = \vec{\Theta}'\;,$$

where the prime denotes the derivative with respect to $\lambda$, and $\vec{\Phi}'=\Phi\vec{1}$ and $\vec{\Theta}'=\Theta\vec{1}$ are real vectors containing the derivatives of the $\phi_k$ and $\theta_j$, respectively.

If we now take the perspective that we have reached a solution $\Phi$, $\Theta$ at a certain $\lambda$ and want to determine how $\Phi$ and $\Theta$ need to change with respect to $\lambda$ to maintain the condition along the path, then we can consider everything except for $\vec{\Phi}'$ and $\vec{\Theta}'$ as given, and we obtain a linear system of $N$ complex equations for the $2N$ real variables $\phi'_k$ and $\theta'_j$, which will have a unique solution in the general case. If we could somehow show that the system cannot become singular, it would follow that we have a well-defined and well-behaved system of first-order differential equations which for given initial conditions determines a unique solution for the $\phi_k$ and $\theta_j$ as a function of $\lambda$. Since we can start out with arbitrary angles $\phi_k=\theta_k$ at the identity, this would yield an $N$-dimensional family of solutions along each path. In case the system of linear equations can become singular, one might still be able to show that there is at least one member of this family for which it doesn't.

[Edit:] I just realized that that's actually a contradiction; there can't be an $N$-dimensional family of solutions along the path and yet unique derivatives $\phi'_k$ and $\theta'_j$, since the derivatives would differ depending on which family member one moves to. This is resolved by looking at the differentiated condition at the identity (i.e. $\lambda=0$), which we can write as

$$\mathrm{e}^{-\mathrm{i}\Theta}H\mathrm{e}^{\mathrm{i}\Theta}\vec{1}=\vec{\Theta}'-\vec{\Phi}'\;.$$

The right-hand side is real, and that gives a condition on $\vec{\Theta}$ (and hence on $\vec{\Phi}=\vec{\Theta}$) at the identity that must be fulfilled in order for $\vec{\Theta}$ to be a suitable starting point for solutions along the path $\mathrm{e}^{\mathrm{i}\lambda H}$. These are $N$ reality conditions for $N$ real parameters, so one might be able to show that this condition has a solution. As for uniqueness, the solution will not be unique if $H$ has a canonical basis vector ( $\vec{e}_j$ with $e_{jk}=\delta_{jk}$) as an eigenvector (meaning that $A$ and $B$ share a basis vector up to phase), and this also leads to corresponding underdetermination in the linear system for $\vec{\Phi}'$ and $\vec{\Theta}'$. Thus if one wanted to use this approach to show uniqueness of the solution (Sam has already shown existence in the meantime), the appropriate conjecture might be that the solution is unique up to an arbitrary phase for each canonical basis vector that is an eigenvector of $H$.

-
Very nice! I'll vote it +1 when I get my votes back sometime tomorrow. –  Carl Brannen Mar 29 '11 at 17:12
@Carl: Thanks :-) What happened to your votes? –  joriki Mar 29 '11 at 17:45
@joriki: There seems to be an upper limit on votes. I don't know since when that feature appeared or if it has always been there. Just discovered it recently. You got my vote in any case! +1 –  Raskolnikov Mar 29 '11 at 17:58
@joriki; I always use up my 30 votes each day. So sometimes I have to keep a link to stuff I want to vote on the next day. –  Carl Brannen Mar 30 '11 at 4:39
@Carl: I've edited the answer with a correction and some thoughts about uniqueness. –  joriki Mar 30 '11 at 8:13

I have a straightforward proof for the case $N = 3$ at http://www.prespacetime.com/index.php/pst/article/view/58 .

-
Thanks for providing this link; I couldn't find it when I was typing up the question. –  Carl Brannen Apr 3 '11 at 22:22

I've written a physics paper, "Unitary Mixing Matrix Theory" (for submission to Jour. Math. Phys.) that uses Sam Lisi's proof. I translated the proof into "physics language", and it's not unlikely that I missed something. See section II, "Hamilton's Equations". For completeness, here's the current version:

An Hermitian matrix generates a 1-parameter subgroup of unitary matrices and any unitary matrix is an element of such a 1-parameter subgroup. Since we are translating the problem into classical mechanics we will use $t$ for the parameter. Thus:
$$U(t) = \exp(it\;H).$$ and the unitary matrix of interest is given by $U(1)$. Given an initial state $\vec{v}(0)$, the state at time $t$ is defined by a set of coupled ordinary differential equations:
$$\vec{v}(t) = U(t)\vec{v}(0) = \exp(it\;H)\vec{v}(0)$$

The 1-parameter subgroup (and therefore the unitary matrix) are fully defined by the relationship between $\vec{v}$ and $\dot{\vec{v}}$. In components:
$$\dot{v}_j = i\Sigma_k H_{jk}\;v_k.$$ Replace the complex variables with real and imaginary parts:
$$v_k = p_k + iq_k$$ $$H_{jk} = r_{jk}+is_{jk}$$ If these are compatible with a Hamiltonian $\mathbf{H}$, we have Hamilton's equations:
$$\dot{q}_j = +\partial \mathbf{H}/\partial p_j = \Sigma_k(+r_{jk}p_k-s_{jk}q_k),$$
$$\dot{p}_j = -\partial \mathbf{H}/\partial q_j = \Sigma_k(-r_{jk}q_k-s_{jk}p_k).$$
Compatibility requires that $s_{jk}=-s_{kj}$, which is true since $H$ is Hermitian. Integrating gives the Hamiltonian as: $$\mathbf{H} = \Sigma_{j\neq k}(r_{jk}(p_jp_k+q_jq_k)+s_{jk}p_kq_j)+\Sigma_{j}r_{jj}(p_j^2+q_j^2)/2.$$ This Hamiltonian, integrated for a period of time $t$, gives the unitary transformation $U(t)=\exp(iHt)$. Note that $\mathbf{H}$ is quadratic in momentum and position and so is a generalization of an harmonic oscillator.

Mathematicians study these Hamiltonians under the label "symplectic geometry." Here we give a brief and rough introduction to the mathematical language. Let $\{\hat{e}_j\}$ be a basis for the positions as a vector space. That is, given a position $\vec{q}=(q_1,q_2,...q_n)$, we treat the sum $\Sigma_j\hat{e}_jq_j$ as an element of a vector space. Similarly, let $\{\hat{f}_k\}$ be a basis for the momenta also with $n$ elements. Combining the two basis sets gives a basis for a $2n$-dimensional vector space $M$. Now define a bilinear map $\Omega$ on $M$ which acts on the basis sets as follows: $$\Omega(\hat{e}_j,\hat{e}_k)=\Omega(\hat{f}_j,\hat{f}_k)=0,$$ $$\Omega(\hat{e}_j,\hat{f}_k)=-\Omega(\hat{f}_k,\hat{e}_j)=\delta{jk}.$$ Without $\Omega$, $M$ is the usual "phase space" of the physicists but the mathematicians prefer to call the combination a "symplectic vector space."

The map $\Omega$ can be thought of as a way of associating positions with momenta. That is, given two elements $u,v$ of $M$ with $\Omega(u,v)=1$, we can think of $u$ as a position and $v$ as its associated momentum. For example, if $\Omega(q_1,p_1)=1,$ then $\Omega(p_1,q_1)=-1$ so $\Omega(p_1,-q_1)=1$. Thus we can think of $p_1$ as a position and $-q_1$ as its associated momentum. This use follows the sense of the usual canonical (or contact) transformations familiar to classical mechanics. This example is one that is typically given in textbooks on the subject; we can swap a position for its associated momentum provided we introduce a minus sign.

Classical mechanics is about the movement of systems through phase space. Suppose a system begins at some particular position. A question of interest is "can the system return to that position at time $t$?" To answer this question, we consider a fixed position with all possible momenta. But Hamilton's equations can be transformed in ways that mix position and momentum. So to understand these questions we need a definition of "initial position" that allows for any possible transformation of Hamilton's equations.

If phase space is not transformed, then the appropriate elements of $M$ to consider are those with particular position and any momentum. This is easy to define by the $\hat{e}_j,\hat{f}_k$ basis elements; we let momentum be in the subspace spanned by the $\hat{f}_k$. Such a subspace has dimension $n$, just half that of $M$. More generally, consider the momentum subspace resulting from any canonical transformation along with a specification of position. Such a subset of $M$ defines an initial value problem in classical mechanics; the mathematicians call such a subset a "Lagrangian submanifold".

We now consider the canonical transformation from $q_j,p_j$ to $\rho_j,\sigma_j$ generated by: $$F = \left(q_j\sqrt{\rho_j^2-q_j^2}+\rho_j^2\sin^{-1}(q_j/\rho_j)\right)/2.$$ This gives $p_j$ and $\sigma_j$ as: $$p_j = \partial F/\partial q_j = \sqrt{\rho_j^2-q_j^2},$$ $$-\sigma_j = \partial F/\partial \rho_j = \rho_j\sin^{-1}(q_j/\rho_j).$$ Solving for $p_j$ and $q_j$ in terms of $\sigma_j$ and $\rho_j$ we have: $$p_j=\rho_j\cos(\sigma_j/\rho_j),$$ $$q_j=\rho_j\sin(\sigma_j/\rho_j).$$ Putting $\rho_j=1$ in the new coordinates defines a Lagrangian submanifold of $M$ for which $\rho_j^2=p_j^2+q_j^2=1.$ And this subset of phase space corresponds to the vectors of phases in Hilbert space. The new momentum consists of a product of $n$ copies of complex phases so it can be called a torus; since it is also Lagrangian, it is a "Lagrangian torus". The torus as we've defined it has a phase freedom. That is, if we add the same phase $\alpha$ to all the $\sigma_j$, the result will be a new vector that is also a vector of phases and that represents the same quantum state. This is just the usual arbitrary complex phase present in a quantum state vector. To eliminate it, the mathematicians prefer to identify equivalent vectors and so work with the equivalent torus in $CP^{n-1}$.

Cheol-Hyun Cho3 refers to our $CP^{n-1}$ torus as a "Clifford torus", an extension of the usual definition. His paper is perhaps the first proof that a Hamiltonian flow cannot "displace" such a torus, that is, move it in such a way that it no longer intersects with itself. Other papers that prove the existence of the intersection are [4,5] and it can be deduced from [6-8]. This completes the proof that an unbiased state exists for two bases. In addition, computer calculation with random unitary matrices failed to find any counter examples and Philip Gibbs[9] proved the $n=3$ case in 2009.

3 C.-H. Cho, “Holomorphic discs, spin structures, and ﬂoer cohomology of the Clifford torus,” Int. Math. Res. Not. 35, 1803–1843 (2004), math / 0308224.
4 P. Biran and O. Cornea, “Lagrangian quantum homology,” The Yashafest, Stanford (2007), math.SG / 0808.3989.
5 P. Biran and O. Cornea, “Rigidity and uniruling for lagrangian submanifolds,” Geom. Topol. 13, 28812989 (2009), math.SG / 0808.2440.
6 C.-H. Cho and Y.-G. Oh, “Floer cohomology and disc instantons of lagrangian torus ﬁbers in fano toric manifolds,” Asian J. Math. 10, 773–814 (2006), math / 0308225.
7 M. Entov and L. Polterovich, “Quasi-states and symplectic intersections,” Eur. Math. Soc. 81, 75–99 (2006), math / 0410338.
8 K. Fukaya, Y.-G. Oh, H. Ohta, and K. Ono, “Lagrangian ﬂoer theory on compact toric manifolds: survey,” (2010), math.SG / 1011.4044.
[9] P. Gibbs, “3x3 unitary to magic matrix transformations,” (2009), vixra 0907.0002.

-