Quantum Circuit Cutting - with Randomly Applied Channels
Recently, I briefly introduced what circuit cutting is, why it is an advisable thing to do with current quantum hardware (NISQ devices) and what additional costs the cutting is causing. However, I did not go into detail how such a circuit cutting method can look like in detail - this is what this entry will be about. In particular, we will have a look on the circuit cutting procedure proposed by Lowe et. al. [1] in which randomly applied channels are able to cut a circuit.
As mentioned in the previous entry, circuit cutting requires to find a proper identity channel on the cut wires which has reasonably low sampling overhead - the definition of the identity is thus the heart of every circuit cutting procedure. In general, such an identity has the form
where Φ_i is some properly chosen quantum channel. The corresponding cost depends on the value κ
which is the L1 norm of the real coefficients of the identity channel above:
Thus, we see that the main possibility to reduce the sampling overhead is to reduce this value. One possibility with small sampling overhead is the following (however, it is not minimal! The method described in [2] has a lower overhead, but we will not go into detail of this).
The identity channel used in [1] looks like
Here, d=2^k is the dimension of the subspace governing the qubits of the cut. The variable z denotes a Bernoulli random value where z=1 appears with probability d/(2d+1). Later, we will derive this form of the identity channel and will see how this probability and also the expectation E_z emerges. Since, there are two values of z, there are also two quantum channels which can be applied. The first one, Ψ_0, is a measure-and-prepare channel:
The unitaries which are applied on the state prior to measurement have to comprise a 2-design (at least) because otherwise the derivation would not work. Such a design is formed by e.g. Clifford gates but there are many possibilities, one could also rely on approximate designs. Since the form of a quantum channel is not so pictorially, you can see in the following how this channel looks like in "circuit-language":
This means, one applies U^\dagger on the k cut wires, measures in z-basis and retrieves a bitstring y. A state in computational basis corresponding to this bitstring gets initialized and then U is applied. All of this is repeated many times.
Note that applying such a circuit in the middle of a larger circuit destroys entanglement of the global state and this is also the reason why cutting requires a lot of sampling (quantified by the sampling overhead): The effects of entanglement in the final result must be regained somehow by repeating the procedure numerous times.
The other channel, Ψ_1, is a simpler one. It is the so-called fully depolarizing channel in which all of the information within the cut (within a sample) is lost:
In practice, the action on the cut part of the circuit is as follows: First one measures the k cut wires in the computational basis. Afterwards one takes a uniformly sampled bitstring x and initializes it on the wires - as in the following circuit snippet:
Guiding through the Derivation
Now, as we have settled the definitions, let's go through the derivation of this identity channel! At first, we need an equation which we shall not prove as this would be more involved (based on Haar measure etc.). It is called Werner Twirling Channel:
This equation is particularly nice because the right hand side is much much simpler than the left hand side, which requires all of the unitaries in the design. At the same time, the right hand side could be quickly written out by hand for e.g. d=1. This will come in handy in deriving the identity channel.
The idea of the proof is to start with one channel Ψ_0 and massage it a little to find an expression of Ψ_1 within it and then massaging it a little further and finding an expression for the identity channel.
Hence, start with the channel Ψ_0:
A lot is going on here, thus let's go through the equalities step by step: From the first to the second line the only thing happening is that we insert an identity (using completeness of the computational basis). Going to the next line, the two scalar factors are swapped and the states with index i can be used to rewrite the expression into a Tr. By exploiting the properties of tensor products and the trace, one can draw outside the sum a partial trace expression in the last line. This shape is nice, because we can recognize the left hand side of the above equation and can simplify the underbraced expression:
Since the expression within the sum does not depend on the index j anymore, this sum merely gives a factor d. In the second line we draw the partial trace factor into the brackets and recognize the Ψ_1 channel! Additionally, the part with the SWAP operator can be simplified as well (you can easily prove this by checking it with a 4x4 SWAP matrix and using a general matrix X). All of this helped us immensely in relating both channels to each other. Reshaping this equation a little gives us:
In the second line, we draw a factor outside in order to retrieve the Bernoulli probabilities we have defined previously and then, by respecting the additional sign, this can be easily rewritten as an expectation value in the last line.
Now as we have both defined and derived the identity circuit expression, let's relate it to the introducing sentences about the sampling overhead. The value of κ can be easily computed:
As we can see, the sampling overhead is exponential in the number of cut qubits - this is a deficit in practice. Even though, there are slightly better circuit cutting procedures, the overhead always scales exponentially in the number of cut qubits. Although unfortunate, this makes perfect sense intuitively: The cutting destroys part of the quantum properties of the system and these must be reproduced classically (by sampling). Mostly everything quantum which is simulated classically scales exponentially (since the Hilbert space dimension grows exponentially with growing number of particles).
Overall, circuit cutting is an interesting new field in quantum computing which might help to go beyond the capabilities of current NISQ devices - nevertheless, there is always a price to pay and it will become evident in future research whether circuit cutting will be a common method or not.
---
References:
[1] Angus Lowe, Matija Medvidović, Anthony Hayes, Lee J. O'Riordan, Thomas R. Bromley, Juan Miguel Arrazola, Nathan Killoran. Fast quantum circuit cutting with randomized measurements. 2022. arXiv:2207.14734
[2] Hiroyuki Harada, Kaito Wada, Naoki Yamamoto. Optimal parallel wire cutting without ancilla qubits. arXiv:2303.07340
