How to compactly represent multiple qubit states?

Question

Since access to quantum devices capable of quantum computing is still extremely limited, it is of interest to simulate quantum computations on a classical computer. Representing the state of $n$ qubits as a vector takes $2^n$ elements, which greatly restricts the number of qubits one can consider in such simulations.

Can one use a representation¹ that is more compact, in the sense that it uses less memory and/or computational power than the simple vector representation? How does it work?

While easy to implement, it is clear that the vector representation is wasteful for states that exhibit sparsity and/or redundancy in their vector representation. For a concrete example, consider the 3-qubit state $(1/\sqrt{3}, 1/\sqrt{3},0,0,0,-1/\sqrt{3}, 0,0)^T$. It has $2^3$ elements but they only assume $3$ possible values, with most of the elements being $0$. Of course, to be useful in simulating a quantum computation we would also need to consider how to represent gates and the action of gates on qubits, and including something about these would be welcome, but I would be happy to hear just about qubits too.

_{1. Notice that I am asking about the representations, not software, libraries or articles that might utilize/present such representations. If you present and explain a representation you are very welcome to mention where it is already used though.}

Answer 1

There are many possible ways to compactly represent a state, the usefulness of which strongly depends on the context.

First of all, it is important to notice that it is not possible to have a procedure that can map any state into a more efficient representation of the same state (for the same reason why it is obviously not possible to faithfully compress any 2-bit string as a 1-bit string, with a mapping that does not depend on the string).

However, as soon as you start making some assumptions, you can find more efficient ways to represent a state in a given context. There is a multitude of possible ways to do this, so I'll just mention a few that come to mind:

1. Already the standard vector representation of a ket state can be thought of as a "compressed representation", that works under the assumption of the state being pure. Indeed, you need $4^n-1$ real degrees of freedom to represent an arbitrary (generally mixed) $n$-qubit state, but only $2^{n+1}-2$ to represent a pure one.

2. If you assume a state $\rho$ to be almost pure, that is, such that $\rho$ is sparse in some representation (equivalently, $\rho$ is low rank), then again the state can be efficiently characterised. For a $d$-dimensional system (so $d=2^n$ for an $n$-qubit system), instead of using ~$d^2$ parameters, you can have a faithful representation using only $\mathcal O(r d \log^2 d)$, where $r$ is the sparsity of the state (see 0909.3304 and the works that came after that).

3. If you are only interested in a limited number $|S|$ of expectation values, you can find a compressed representation of an $n$-qubit state of size $\mathcal O(n\log(n)\log(|S|))$. Note that this amounts to an exponential reduction. This was shown (I think) in quant-ph/0402095, but the introduction given in 1801.05721 may be more accessible for a physicist (as well as presenting improvements in the optimisation method). See references in this last paper for a number of similar results.

4. If you know that the entanglement of the state is limited (in a sense that can be precisely defined), then again efficient representations can be found, in terms of tensor networks (an introduction is found e.g. in 1708.00006). More recently, it was also shown that ground states of some notable Hamiltonians can be represented using machine-learning-inspired ansatze ( (1606.02318 and many following works). This was also recently shown/claimed to be equivalent to a specific Tensor Network representation however (1710.04045) so I'm not sure whether it should go to a category of its own.

Note that in all of the above, you can more efficiently represent a given state, but to then simulate the evolution of the system you generally need to go back to the original inefficient representation. If you want to efficiently represent the dynamics of a state through a given evolution, you again need assumptions on the evolution for this to be possible. The only result that comes to mind in this regard is the classical (as in established, not as in "non-quantum") Gottesman-Knill theorem, which allows to efficiently simulate any Clifford quantum circuit.

Answer 2

$\newcommand{\ket}[1]{\left|#1\right>}$I'm not sure using sparsity is a good approach here: even single-qubit gates could easily turn a sparse state into a dense one.

But you can use the stabilizer formalism if you only use Clifford gates. Here is a short recap (notation):
The single-qubit Pauli group is $G_1=\langle X, Y, Z\rangle$, i.e. all possible products of Pauli matrices (including $\mathbb{I}$). The Pauli group of several qubits is the tensor product space of $G_1$, $G_n=G_1^{\otimes n}$. The stabilizer of a state $\ket{\psi}$ is the subgroup of the Pauli group of all operators that stabilize $\ket{\psi}$, which means $s \ket{\psi} = \ket{\psi}$. It is important to note that this only works for specific (but important) states. I will give an example below. The restriction to elements of the Pauli group is not necessary but common. The stabilizer is generated by operators $s_1$, $s_2$, ... $s_n$. The stabilizer uniquely defines the state and is an efficient description: instead of $2^n-1$ complex numbers we can use $4n^2$ bits ($G_1$ has 16 elements). When we apply a gate $U$, the stabilizer generators update according to $s_i \to U^\dagger s_i U$. A gate that maps Pauli operators to Pauli operators is called Clifford gates. So these are the gates that will not "mess up" our description of the state.

Graph states are an important example for the stabilizer formalism described above. Consider an (undirected) mathematical graph, which consists of $n$ vertices $V$ and edges $E\subset V\times V$. Each vertex corresponds to one qubit. Let us denote the graph by $G=(V,E)$. A graph state is produced from the state $\ket{+}^{\otimes n}$, where $\ket{+}=\frac{1}{\sqrt{2}} (\ket{0}+\ket{1})$ by applying a controlled-phase gate $C_Z$ for each pair of vertices which are connected. The stabilizer is generated by $$s_v= X_v \prod_{\substack{w\in V\\ (v,w)\in E}} Z_w.$$

For example start with the two-qubit state $\ket{\phi}=\ket{+}\otimes \ket{+}$. The stabilizer is $\langle X\otimes \mathbb{I}, \mathbb{I}\otimes X \rangle$. Now apply the $C_Z$ gate to obtain $\langle X \otimes Z, Z \otimes X \rangle$. (The state is $\ket{\phi'}=\frac{1}{2}(1,1,1,-1)^T$, which is local unitary equivalent to a Bell state)

The stabilizer formalism also plays an important role in quantum error correction.

Answer 3

Can one use a representation that is more compact, in the sense that it uses less memory and/or computational power than the simple vector representation? How does it work?

Source: "Multiple Qubits":

"A single qubit can be trivially modeled, simulating a fifty-qubit quantum computation would arguably push the limits of existing supercomputers. Increasing the size of the computation by only one additional qubit doubles the memory required to store the state and roughly doubles the computational time. This rapid doubling of computational power is why a quantum computer with a relatively small number of qubits can far surpass the most powerful supercomputers of today, tomorrow and beyond for some computational tasks.".

So you can't utilize a Ponzi scheme or rob Peter to pay Paul. Compression will save memory at the cost of computational complexity, or representation in a more flexible space (larger) would reduce computational complexity but at a cost of memory. Essentially what is needed is more capable hardware or smarter algorithms.

---

Here are some methods:

• Compression of the volume of sets of quantum states of the Qubit's metric:

The Fisher information metric can be used to map the volume of the qubit using an information geometry approach as discussed in "The Volume of Two-Qubit States by Information Geometry", "Analysis of Fisher Information and the Cramer-Rao Bound for Nonlinear Parameter Estimation After Compressed Sensing", and our "Intuitive explanation of Fisher Information and Cramer-Rao bound".

• Analogous to operand compression:

Computing depth-optimal decompositions of logical operations: "A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits" or this Quora discussion on "Encoding the dimension of the particle".

• Analogous to memory compression:

Qutrit factorization using ternary arithmetic: "Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures" and "Quantum Ternary Circuit Synthesis Using Projection Operations".

• Analogous to traditional optimization

"A Quantum Algorithm for Finding Minimum Exclusive-Or Expressions".

• Other:

Krull Dimensions or axiomatisation and graph rewriting: "Completeness of the ZX-calculus for Pure Qubit Clifford+T Quantum Mechanics".

By combining those techniques you ought to be able to squeeze the foot into the shoe. That would permit emulation of larger systems on conventional processors, just don't ask me to explain doctoral level work or write the code. :)