What is the Correct State-space for Quantum Computing?

\[\def\ev{\mathrm{ev}} \def\span#1{\operatorname{span}\{#1\}} \def\Hom{\operatorname{Hom}} \def\bra#1{\langle #1|} \def\ket#1{|#1\rangle} \def\ketbra#1{\ket{#1}\bra{#1}} \def\MS{\text{MS}} \def\BC{\mathbb{C}} \def\BP{\mathbb{P}} \def\tr{\operatorname{tr}} \def\abs#1{\lvert #1\rvert}\]

A couple of weeks ago, I decided to spend a few days looking in the hidden subgroup problem and quantum computing. I had long heard the standard memes of quantum computing: Shor’s algorithm breaks factoring/DLP, Grover’s algorithm has a generic $\sqrt{N}$ speedup, and that lattice-based cryptography is our only hope for post-quantum public-key cryptography. But here and there I heard another meme: Shor’s breaks factoring/DLP via abelian group HSP (hidden subgroup problem), and lattice-cryptography reduces to dihedral group HSP.

So, I set out to understand quantum computing from an algorithm-designer perspective and what was going on with the hidden subgroup problem. While I used a lot of sources, this one by Childs and Van dam was probably the most useful. All of this would culminate in a suspect-quality series of videos I made here. Along the way I had a couple thoughts on the state-space and mixed-states.

Quick Rundown of the Quantum Computing Model and States

Let $(H,\langle ,\rangle)$ be a finite-dimensional Hilbert space. Without loss of generality, this is $(\mathbb{C}^N, \langle,\rangle)$ where the inner product is the standard inner product. We write the standard basis in bra-ket notation with $\ket{i}$ kets. We’ll model quantum computation as follows:

Computing:

1. Initialize: We start with a state $\ket{\psi}\in H$
2. Evolve: Apply a unitary operator $U$ to the state $\ket{\phi} = U\ket{\psi}$
3. Measure: Normalize $\ket{\phi}$ such that it has unit norm. Then we can write \(\ket{\phi} = \sum_i \alpha_i\ket{i}\) such that $\abs{\alpha_i}^2$ are nonnegative numbers which sum to $1$. We observe $i$ with probability $\abs{\alpha_i}^2$ on measurement.

Immediately from this, we see that a state is equivalent to its normalized state as unitary operators preserve norms. Thus, we can reduce our state space to $S(H)\subset H$: the subset consisting of unit vectors. Most texts call this the state space but we can further reduce by modding out by global phase. That is, any $\ket{\psi}$ is equivalent in observed behavior to $\omega \ket{\psi}, \omega \in U(1)$. This has the collective effect of reducing our state space to $\mathbb{P}(H)$, the projectivization of $H$. Is this the true

Exercise: Show that this is the correct state space by showing that any two states $\ket{\psi}\neq \ket{\phi}$, there exists a unitary $U$ such that measuring after applying $U$ to each of these states yields different probability distributions.

The Qubit: For the qubit, one has $H = \mathbb{C}^2$, $S(H) = S^3$, and $\mathbb{P}(H) = \BC\BP^1$.¹ For $n$ qubits, we have $H = (\BC^2)^{\otimes n}$, and state-space $\BC\BP^{2^n-1}$. In practice, for working with states it is often easiest to work with representatives in $H$ and normalize on/off when convenient.

Mixed States

Mixed states are meant to model the combination of classical probability with quantum states. That is, how do we represent a probability distribution over quantum states? Well, the simplest solution is to represent it with a probability distribution $\mu$ over quantum states $\BP(H)$. However, the space of probability distributions over $\BP(H)$ is quite unwieldy. It also over-specifies things. For one, many distributions have equivalent behavior: Under any computation they yield the same probability distribution.

Exercise: Show that this is true for the following distributions on one qubit: $(\ket{0}, \ket{1})$, and $(\ket{0}+\ket{1},\ket{0}-\ket{1})$ where both of these probability distributions are 50-50 chances for the two respective quantum states.

The standard way one represents mixed states is via density matrices:

\[D = \sum_i p_i \ketbra{\psi_i}\in \text{End}(H,H)\]

The element $\bra{\psi}\in V^\ast$ represents the linear map $\langle \psi, -\rangle$.² We get a natural map \(\MS:\mathbb{P}(H)\rightarrow \text{End}(H,H)\) by sending $\ket{\psi}$ to $\ketbra{\psi}$. We can do evolution by $U$ via $D\mapsto UDU^\dagger$ and measure with respect to a standard basis element by $A_i= \ketbra{i}$.

\[\begin{align*} \tr(A_i D) &= \sum_j p_j \langle i, \psi_j\rangle\langle \psi_j, i\rangle\\ &= \sum_j p_j |a_{ij}|^2 \end{align*}\]

where $\abs{a_{ij}}^2$ is the probability that $\psi_j$ yields $i$ when measured with respect to the standard basis. We’ll henceforth denote the map that gives us the probability of observing $i$ after applying $U$ to a mixed-state as $\lambda_{i,U}$.

\[\lambda_{i,U}(D) = \tr(A_i UDU^\dagger)\]

Thus, density matrices model discrete probability distributions over states. Remarkably, they also work for continuous distributions too. If we have a probability distribution $\mu$ over $\BP(H)$, we can calculate the probability that one measures $i$ after applying $U$ via the following integral

\[\int_{\mathbb{P}(H)} \lambda_{i,U}(\MS(\psi))\mathrm{d}\mu(\psi)\]

As $\lambda_{i,U}$ is linear and $\BP(H)$ is compact, we can factor it out, and we get that this integral is equal to

\[\lambda_{i,U}\left(\int_{\BP(H)} \MS(\psi)\mathrm{d}\mu(\psi)\right)\]

That is, we can extend $\MS$ to all probability distributions on $\BP(H)$ and the extension will correctly derive the probability one gets $i$ after applying $U$ and measuring via applying $\lambda_{i,U}$. This is quite a compression. We have gone from a space of all probability distributions on a manifold to a convex subset of a finite-dimensional vector space. Every probability distribution over $\BP(H)$ is equivalent to one with discrete distribution orthogonal states. The question remains, is this the final step? Are there any more relations we can shave off?

Exercise: Given two non-equal mixed states, $D_1, D_2$, show that there is some $i,U$ such that $\lambda_{i,U}(D_1) \neq \lambda_{i,U}(D_2)$.

Footnotes