Quantum circuit cutting

Quantum circuit cutting is a method to partition a large quantum circuit into smaller, more manageable parts. In particular, during the NISQ era of quantum computing the execution of quantum circuits is limited by the size, i.e., number of qubits, as well as their high susceptibility to noise. Therefore it is desirable to partition a quantum circuit into smaller chunks, run them on possibly smaller quantum devices and then to perform postprocessing to retrieve results which are close to the results one would expect from the uncut circuit. It has been shown in experiments, that the application of circuit cutting can indeed reduce the impact of noise.

Quasi probability decomposition

Visualization of quantum circuit cutting for wire and gate cutting

In order to perform wire or gate cutting, one can decompose the quantum channel ${\mathcal {V}}$ of the operation to cut as quasi probability decomposition

$${\mathcal {V}}(\rho )=\sum _{i}a_{i}\Phi _{i}(\rho )$$ with coefficients $a_{i}\in \mathbb {R}$ such that $\sum _{i}a_{i}=1$. Those coefficients can be either positive or negative which is why this is coined as quasiprobability distribution. The $\Phi _{i}$'s are quantum channels which can act on disjoint qubits in the case of gate cutting, i.e., $\Phi _{i}(\rho ^{A}\otimes \rho ^{B})=\Phi _{i}^{A}(\rho ^{A})\otimes \Phi _{i}^{B}(\rho ^{B})$, where $A,B$ denote the partitions resulting from the cut. For the case of wire cutting, the $\Phi _{i}$'s are measure-and-prepare-channels. Therefore, in the case of gate cutting the channel ${\mathcal {V}}$ is the channel of some quantum gate and for wire cutting it is the identity channel, as quantum wires act as identities on the qubits.

Sampling overhead

Cutting a circuit comes with the prize of a sampling overhead, scaling exponentially in the number of qubits involved in the cut. The sampling overhead depends on the L1 norm of the coefficients, i.e., $\kappa =\sum _{i}|a_{i}|$. From Hoeffding's inequality one can derive that the number of samples needed to retrieve an expectation value of the cut circuit which is close to the result expected from the uncut circuit scales as ${\mathcal {O}}(\kappa ^{2})$.

The value $\kappa$ scales exponentially with the number of cuts and therefore imposes a serious limitation on circuit cutting techniques. Thus, it is desired to reduce this value as much as possible. Considering the cut of $n$ parallel qubit wires, the method proposed by Peng et al. requires $\kappa ^{2}=16^{n}$. It was argued that the usage of classical communication between the different partitions can reduce the sampling overhead. The cutting technique introduced by Harada et al. employs classical communication and requires $\kappa ^{2}=(2^{n+1}-1)^{2}$ which is the lowest possible if LOCC is used.

Quasi probability sampling

In order to execute a circuit which is decomposed by one or more cuts, one performs quasi probability sampling. This is a type of Monte Carlo Sampling. Depending on the number of total shots $n$, one determines the number of shots $n_{i}$ required for each channel $\Phi _{i}$. Each channel must be sampled with a probability $p_{i}={\frac {|a_{i}|}{\kappa }}$, therefore $n_{i}=np_{i}$. One runs the cut circuits with the aforementioned distribution of channels $\Phi _{i}$ and stores the results. Note that if a cutting scheme requires LOCC this must be taken into account in the sampling process.

For example, one can consider an observable which is diagonal in the Pauli Z basis, $O_{f}=\sum _{x\in \{0,1\}^{n}}f(x)|x\rangle \langle x|$ with some function $f:\{0,1\}^{n}\rightarrow \mathbb {R}$. In this case, one can measure all qubits of the partitioned circuit in the computational basis, recombine the bitstring outcomes and apply the function $f$. The results for each sample are stored and further classical post processing is applied: Multiply a weight $\kappa \,\mathrm {sgn} (a_{i})$ to each result and compute the mean over all samples. This way one retrieves the result of an unbiased estimator of the uncut expectation value. Note that this can be done in principle for general observables.

Example cutting technique: Peng et al.

Peng et al. introduced wire cutting in 2020. Their proposed technique cuts quantum wires with local operations only. It makes use of the fact that density matrices can be decomposed into the Pauli basis. For cutting a single quantum wire, the Quasi Probability Decomposition can be expressed as

$${\mathcal {V}}(\rho )=\mathrm {Id} (\rho )=\sum _{i=1}^{8}a_{i}\Phi _{i}(\rho )$$ More specifically, one defines $$\Phi _{i}(\rho )=\mathrm {tr} (\rho O_{i})\rho _{i}$$ where each $\rho _{i}$ are projectors onto the eigenbases of the Pauli matrices. Each $a_{i},O_{i},\rho _{i}$ are defined as

$O_{i}$	$\rho _{i}$	$a_{i}$
$O_{1}=I$	$\rho _{1}=|0\rangle \langle 0|$	$a_{1}=+1/2$
$O_{2}=O_{1}$	$\rho _{2}=|1\rangle \langle 1|$	$a_{2}=+1/2$
$O_{3}=X$	$\rho _{3}=|+\rangle \langle +|$	$a_{3}=+1/2$
$O_{4}=O_{3}$	$\rho _{4}=|-\rangle \langle -|$	$a_{4}=-1/2$
$O_{5}=Y$	$\rho _{5}=|i\rangle \langle i|$	$a_{5}=+1/2$
$O_{6}=O_{5}$	$\rho _{6}=|-i\rangle \langle -i|$	$a_{6}=-1/2$
$O_{7}=Z$	$\rho _{7}=|0\rangle \langle 0|$	$a_{7}=+1/2$
$O_{8}=O_{7}$	$\rho _{8}=|1\rangle \langle 1|$	$a_{8}=-1/2$

where $|0\rangle ,|1\rangle ,|+\rangle ,|-\rangle ,|i\rangle ,|-i\rangle$ are the eigenstates of the Pauli matrices.

Example application: QAOA for MaxCut

As quantum circuit cutting is inherently limited by its exponential sampling overhead, applying circuit cutting to general circuits can be rendered ineffective. Therefore it is often useful to consider particularly suitable problems for quantum circuit cutting. Cutting is often applied to NISQ algorithms such as QAOA. QAOA can be used to solve the maximum cut problem. Since qubits and two-qubit gates in the QAOA circuit's problem layer can be considered as representatives of the Maximum cut's problem graph, the graph's structure can be seen directly in the QAOA circuit: Qubits are nodes and gates edges of the problem graph. Therefore, QAOA circuits for problem graphs with specific structure are particularly suitable to be partitioned via quantum circuit cutting. One such class of graphs, as suggested by Lowe et al. are those with vertex separators. If the circuit is cut along the qubits corresponding to the vertex separators (with limited number of size), the sampling overhead can be kept reasonably small.