Quantum Computing

Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Developing new algorithms requires concepts and tools that are able to express the logic behind complex quantum circuits and translate classical mathematical operations into instructions that can be executed on quantum computers and vice versa. Due to its significance for understanding the computational benefits and developing new algorithms, the numerical simulation of quantum computers on classical hardware is of utmost importance. To provide a framework for the description of quantum circuits in matrix product state (MPS)/ matrix product operator (MPO) format, let us first recapitulate the basic representation of quantum registers comprising multiple qubits. In what follows, we will consider computational basis states of the form

$$\left| x \right\rangle = \left|x_1 x_2 \dots x_n \right\rangle = \left|x_1\right\rangle \otimes \dots \otimes \left|x_n\right\rangle,$$

with $x_i \in \{0,1\}$, in lexicographical order, i.e.,

where $\left|0\right\rangle = [1, 0]^\top$ and $\left|1\right\rangle = [0,1]^\top$. A quantum state of $n$ qubits can then be written as

$$\left|\psi\right\rangle = \sum_{x_1, \dots , x_n = 0}^1 \mathbf{\Psi}_{x_1, \dots, x_n} \cdot (\left|x_1\right\rangle \otimes \dots \otimes \left|x_n\right\rangle), $$

where the tensor $\mathbf{\Psi} \in \mathbb{C}^{2^{\times n}}$ represents the wave function, i.e., it contains the probability amplitudes corresponding to each basis state such that $\sum_{x_1,\dots, x_n=0}^{1} \left|\mathbf{\psi}_{x_1, \dots, x_n}\right|^2 = 1$.

A quantum state is called separable if it can be written as a rank-one tensor, i.e., as a tensor product of $n$ components. But we are interested in expressing not only separable but also highly entangled quantum states with the aid of tensor products. To this end, we employ the MPS format to represent quantum state as well as quantum gates and entire circuits as low-rank tensor networks. This allows us to analyze and simulate complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. For instance, one of the most important controlled logic gates is the controlled NOT gate which can be expressed in canonical format as

$$\mathrm{CNOT} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} \otimes I + C \otimes \sigma_x = I^{\otimes 2} + C \otimes (\sigma_x-I) \cong \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}.$$

Here, $C$ denotes the control matrix and $\sigma_x$ the Pauli-$X$ gate, given by

$$C = \begin{bmatrix} 0 & 0 \\ 0 & 1\end{bmatrix} \quad \text{and} \quad \sigma_x = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}.$$

However, we can construct compact MPO expressions of gates acting on two or more qubits, even if these are not adjacent. Any controlled gate acting on a quantum register with $n$ qubits has a rank-$2$ representation of the form

$$\mathbf{G} =I^{\otimes n} + I^{\otimes (p-1)} \otimes C \otimes I^{\otimes (q-p-1)} \otimes (A - I) \otimes I^{\otimes (n-q)}$$

where $p$ is the position of the control qubit and $q$ the position of the target qubit. Note that any (multi-)control quantum gate can be represented by a tensor with canonical and MPS ranks bounded by $2$. Given a quantum circuit and an initial quantum state in form of an MPO $\mathbf{G} \in \mathbb{C}^{D \times D}$ and an MPS $\mathbf{\Psi} \in \mathbb{C}^D$, respectively, the product $\mathbf{G} \mathbf{\Psi}$ representing the final quantum state is given by

$$\begin{aligned}\mathbf{G} \mathbf{\Psi} &= \left( \sum_{k_0, \dots, k_n =1}^{R_0, \dots, R_n} \bigotimes_{i=1}^n \mathbf{G}^{(i)}_{k_{i-1}, :,:, k_i} \right) \left( \sum_{\ell_0, \dots, \ell_n=1}^{r_0, \dots, r_n} \bigotimes_{i=1}^n \mathbf{T}^{(i)}_{\ell_{i-1}, :, \ell_i} \right) \\ &= \sum_{k_0, \dots, k_n =1}^{R_0, \dots, R_n} \sum_{\ell_0, \dots, \ell_n=1}^{r_0, \dots, r_n} \bigotimes_{i=1}^n \left( \mathbf{G}^{(i)}_{k_{i-1}, :,:, k_i} \mathbf{T}^{(i)}_{\ell_{i-1}, :, \ell_i} \right)\end{aligned}.$$

The probability distribution for measuring each basis state can then either be constructed directly as a tensor or efficiently sampled by using a generative sampling strategy.

In [1], we have shown how to systematically decompose quantum gates acting on arbitrary qubits. The techniques proposed in our paper introduce a new framework for designing and simulating complex quantum circuits as they provide access to them via closed-form operator representations. Our numerical experiments showed that the MPO-based construction of quantum algorithms is not only equivalent in terms of simulation results but also may allow us to speed up computations by exploiting the coupling structure of low-rank tensor decompositions.

[1] P. Gelß, S. Klus, Z. Shakibaei, S. Pokutta. Low-rank tensor decompositions of quantum circuits. arXiv: 2205.09882