Why can all quantum circuits be converted into circuits that use only real matrices?

Question

I know that you need to add an additional ancilla qubit to "keep track" of whether or not you are in real space or imaginary space, but how exactly does this work?

What is the proof for this? I tried looking online but I could not find a proof. I only found statements such as "dedicate an extra qubit for the complex subspace".

Can someone please explain the intuition behind this, and also provide the proof?

Thanks for the help!

Answer 1

The fact that "we need work only with quantum Turing machines (QTMs) with real-valued transitions" is proved by Bernstein and Vazirani in their paper Quantum complexity theory (1993).

Aharonov in her paper A Simple Proof that Toffoli and Hadamard are Quantum Universal (2003) provided the following simple explanation:

1. Add one extra qubit to the circuit, the state of this qubit indicates whether the system's state is in the real or imaginary part of the Hilbert space.
2. Replace each gate $U$ acts on $k$ qubits and has complex entries in its matrix representation by its real version, denoted $\hat{U}$, which operates on the same $k$ qubits plus the extra qubit. $\hat{U}$ is defined by:

$$\hat{U}|i\rangle|0\rangle = \hspace{3mm} Re(U)|i\rangle|0\rangle + Im(U)|i\rangle|1\rangle$$

$$\hat{U}|i\rangle|1\rangle = −Im(U)|i\rangle|0\rangle + Re(U)|i\rangle|1\rangle$$

Here $Re(U)$, $Im(U)$ means the real and the imaginary part of the matrix $U$, respectively. The new circuit computes the same function with the overhead of one qubit.

Answer 2

As Mark notes, the result is quite old, possibly dating back to the 90s. However, a quick search yields this paper, which briefly discusses this result. Then it cites this thesis for proofs.

Technical details aside, the intuition why this is true is quite simple. A complex vector $v$ can always be transformed into a larger real vector $[v]_r$, which contains the same information. The easiest way of doing this is to create a vector of double size, where half the entries contain the real part and the other half the imaginary part of $v$.

Similarly, we can figure out how to transform a complex gate's matrix $G$ into larger real matrix $[G]_r$, such that $[G]_r[v]_r = [Gv]_r$. This should always be possible because everything is a linear transformation.

If we do this for every gate in a universal gate set, then we can transform any quantum circuit into an equivalent one where we always remain within the real space. The only trouble I foresee, is that measurements are non-linear processes and getting their equivalence might require some thought.

Answer 3

To give a more general perspective on this: in linear algebra in general you can replace complex numbers with real numbers by enlarging the space and suitably redefining operations.

A simple way is to send any vector $v\in\mathbb{C}^n$ into $\tilde v\equiv \binom{v_R}{v_I}\in\mathbb{R}^{2n}$, with $v_R,v_I\in\mathbb{R}^n$ denoting real and imaginary parts of $v$, respectively. Then for any complex $n\times n$ matrix $A$, we replace $$A v \to \begin{pmatrix}A_R & -A_I \\ A_I & A_R\end{pmatrix}\begin{pmatrix} v_R\\v_I\end{pmatrix}.$$ You'll notice operating on the "complex" left-hand side or the "real" right-hand side makes no difference. Working on the RHS amounts to computing the LHS keeping track of real/imaginary components of each expression.

Most results expressed for complex objects will get a counterpart for their "realified expressions". For example, an $n\times n$ complex $U$ is unitary iff its realified counterpart is special orthogonal. You have results like $$\det\begin{pmatrix} A_R & -A_I\\ A_I & A_R \end{pmatrix} = |\det(A_R + i A_I)|^2$$ which ensure eigenvalues also behave as they should, etc.

The observation about adding an extra qubit to get real quantities is just a simple way to "simulate" these relations in a circuit.