betaFeedback

WorksPhysics and Astronomy

Optimal joint cutting of two-qubit rotation gates

Abstract

Circuit cutting, the partitioning of quantum circuits into smaller independent fragments, has become a promising avenue for scaling up current quantum-computing experiments. Here, we introduce a scheme for joint cutting of two-qubit rotation gates based on a virtual gate-teleportation protocol. By that, we significantly lower the previous upper bounds on the sampling overhead and prove optimality of the scheme. Furthermore, we show that no classical communication between the circuit partitions is required. For parallel two-qubit rotation gates we derive an optimal ancilla-free decomposition, which include CNOT gates as a special case.

Introduction

Current quantum computing hardware faces serious limitations, such as low qubit numbers and high susceptibility to noise. As a result, quantum hardware will likely be unable to execute algorithms with provable speedup like Shor’s [1] or Grover’s [2] algorithm in the near future. On the other hand, experiments with heuristic quantum algorithms have been conducted on a small number of qubits, primarily applied to toy problems from the fields of, e.g. optimization [3, 4], machine learning [5, 6], and chemical simulations [7, 8]. However, scaling up both problem sizes and the number of qubits is crucial for assessing the potential usefulness of quantum computers. Even though recent progress [9] suggests that quantum hardware based on superconducting qubits might be on the verge of entering a so-called utility regime where the first practically interesting problems might be approached, to achieve relevant hardware size, modular quantum computing has been proposed [10, 11]. In this paradigm, multiple quantum computing platforms are interconnected through quantum links possibly enhanced by virtual entanglement distillation [12, 13]. Until reaching a higher technology readiness level, circuit cutting could serve as a useful approach, replacing quantum links with classical links and a post-processing step.

Given a unitary quantum channel V\mathcal{V}, circuit cutting describes the method of decomposing the channel as

V=∑iaiFi,(1)\mathcal{V} = \sum_i a_i \mathcal{F}_i, \tag*{(1)}

with the real coefficients aia_i, to reduce the circuit size or the impact of noise.

Circuit cutting can be categorized into two methods. Wire cutting [14, 15, 16, 17, 18, 19] effectively corresponds to the cutting of horizontal empty qubit wires which are modeled mathematically by the identity channel. Consequently, wire cutting is a decomposition of this channel into measure-and-prepare channels. The second method, on which the focus will be in this work, is known as gate cutting [20, 21, 22, 23, 24]. Here, Fi\mathcal{F}_i are elements of LOCC⁡(A,B)\operatorname{LOCC}(A,B), that is local operations on two partitions AA and BB

of the quantum circuit and classical communication between them. Since Fi\mathcal{F}_i are local operations, no entanglement is created by the channel, but is effectively simulated as described below. If all wires or gates that connect the partitions AA and BB are cut, the sub-circuits become independent and can be run on two quantum computers only connected by classical communication links. Most circuit-cutting research so far has focused on applications to algorithms where the output is an expectation value of an observable. To evaluate Eq. (1) in this context, we first define κ=∑i∣ai∣\kappa= \sum_i |a_i| and the probability distribution pi=∣ai∣/κp_i = |a_i|/\kappa. Next, Eq. (1) is rewritten as

V=κ∑ipisign⁡(ai)Fi(2)\mathcal{V} = \kappa\sum_i p_i \operatorname{sign}(a_i)\mathcal{F}_i \tag*{(2)}

and evaluated via Monte-Carlo sampling. At each experimental shot we select the iith channel Fi\mathcal{F}_i with probability pip_i and evaluate the circuit with V\mathcal{V} replaced by Fi\mathcal{F}_i. The measurement outcome is weighted by κsign⁡(ai)\kappa\operatorname{sign}(a_i) and the mean over many runs produces an unbiased estimate for the expectation value of the observable. This sampling procedure is referred to as quasi-probability sampling [25] because of the appearance of the sign of aia_i in Eq. (2) which is referred to as a quasi-probability decomposition (QPD).

Quasi-probability sampling incurs a sampling overhead, the factor of more samples required to estimate the expectation value of an observable with the same accuracy as with respect to the original uncut circuit. This sampling overhead has been shown to be κ2\kappa^2 [25, 26] and originates from the factor of κ\kappa in front of the sum in Eq. (2).

Note the similarity of the approach to probabilistic error cancellation where the (possibly unphysical) inverse of a noisy quantum channel is decomposed into physical operations [27].

The application of circuit cutting to sampling tasks has been studied initially in Ref. [17] and recently more extensively in Ref. [28] with the result that circuit cutting can also be meaningful in this situation.

When gates or wires are cut individually, the overall sampling overhead increases exponentially in the number of gates and wires cut. This strong increase of sampling overhead renders circuit cutting prohibitively expensive when the cutting location in a circuit and the cutting scheme is not carefully selected. The task is, therefore, to find decompositions of gates or collections of gates with minimal κ\kappa, which we will refer to as γ\gamma.

Ref. [23] employed CNOT-gate teleportation [29, 30, 31] consuming one Bell state initially connecting the two partitions per CNOT gate. The optimal QPD with γ=3\gamma=3 of the Bell-state density matrix then translates into the optimal decomposition of the gate. The crucial insight of Ref. [23] was that the joint QPD of nn Bell states required for the teleportation of nn CNOT gates can be constructed more efficiently compared to the individual decomposition of the gates. As a result, the γ\gamma parameter is reduced from O(3n)O(3^n) to O(2n)O(2^n), however at the cost of one ancilla qubit per partition and gate. In this cutting scheme, Fi∈LOCC⁡(A,B)\mathcal{F}_i \in\operatorname{LOCC}(A,B) and two-way classical information is shared between the partitions. The protocol was extended to general Clifford gates and later also to wire cutting [15]. Recently, it was shown that optimal cutting of parallel wires is possible without ancilla qubits [16].

In this work, we extend previous proposals to the joint cutting of non-Clifford two-qubit rotation gates. We significantly simplify existing methods and, by that, enable implementation on current noisy intermediate-scale quantum (NISQ) hardware. Two-qubit rotation gates play a crucial role for example in the quantum approximate optimization algorithm (QAOA) [4] or for the simulation of spin systems. In Sec. II, we introduce a virtual teleportation scheme that effectively consumes less than one entanglement bit (ebit). After explaining the protocol for a single gate instance, we generalize the scheme to the joint cutting of nn two-qubit rotation gates and demonstrate the optimality of the derived circuit-cutting method. With optimality, we refer to the circuit cutting scheme based on quasi-probability sampling with the minimal possible sampling overhead. A two-qubit rotation gate with rotation angle θ\theta is defined as

RZZ(θ)=cos⁡(θ/2)I⊗I−isin⁡(θ/2)Z⊗Z(3)R_{ZZ}(\theta)=\cos(\theta/2)I\otimes I-i\sin(\theta/2)Z\otimes Z \tag*{(3)}

with the single-qubit identity II and the Pauli ZZ matrix. The γ\gamma parameter for this gate is [21, 23]

γ=1+2∣sin⁡(θ)∣(4)\gamma=1+2|\sin(\theta)| \tag*{(4)}

As we will show, when nn instances of this gate are jointly cut, we will find the reduced effective γ\gamma parameter per gate

γ=1+∣sin⁡(θ)∣(5)\gamma=1+|\sin(\theta)| \tag*{(5)}

asymptotically as nn approaches infinity, which matches the lower bound. Our scheme offers several improvements over previous work. First, it eliminates the need for classical communication between the partitions, and consequently, no real-time feedback is required. This contrasts the gate-teleportation protocol used in Ref. [23] where local correction operators conditioned on intermediate measurement results are necessary. Moreover, as explained in more detail in Sec. II.B our protocol can be executed sequentially on the same quantum computer, unlike schemes where two-way classical communication exchange necessitates the use of two separate quantum computers in parallel. Second, it has recently been emphasized that the number of operations Fi\mathcal{F}_i can be the limiting factor for the execution of circuit-cutting protocols [16]. We derive a quasi-probability decomposition of the entanglement resource states with an exponentially reduced number of elements. Third, in Sec. III, we show that parallel gates can be cut without the need for ancilla qubits. Parallel gates refer to gates that can be executed within the same time slice of a circuit as shown in Figure 1. Note that controlled rotation gates and CNOT gates (for θ=π/2\theta=\pi/2) are equivalent to two-qubit rotation gates up to local operations. Thus, all results of our work also apply to these types of gates.

Figure 1. Cutting of parallel CNOT gates. Consider two partitions AA and BB of a quantum circuit connected by nn CNOT gates. In the case of gates that can be executed at the same time slice of the circuit (parallel gates), we present a joint optimal ancilla-free decomposition with coefficients aia_i and unitary or measurement operations FiA\mathcal{F}_i^A and FiB\mathcal{F}_i^B. The sampling overhead is O(γ2)O(\gamma^2) where γ=O(2n)\gamma= O(2^n). This is a strong improvement compared to cutting nn CNOT gates independently for which γ=O(3n)\gamma= O(3^n). Note that the equality in the figure has to be understood on the superoperator rather than on the gate level.

Virtual gate teleportation

In this section, we aim to find an optimal joint decomposition of two-qubit rotation gates based on gate teleportation. A teleportation scheme for a two-qubit rotation gate RZZ(θ)R_{ZZ}(\theta) [31] is shown in Figure 2. It consumes one initial Bell state (wiggly line in the figure) prepared on two ancilla qubits. These qubits are subsequently measured in the computational basis, and the outcomes, k,l∈{0,1}k,l\in\{0,1\}, are communicated between the partitions AA and BB via classical communication to select the local Pauli correction operators XkX^k and ZlZ^l. For θ=π/2\theta=\pi/2 the two-qubit rotation gate is equivalent to a CNOT gate up to local operations. In this case, simulating the initial Bell state by a quasi-probability distribution with γ=3\gamma=3 translates into an optimal cutting scheme for a CNOT gate (also γ=3\gamma=3) [23].

Figure 2. Teleportation protocol for a two-qubit rotation gate RZZ(θ)R_{ZZ}(\theta) [31]. The scheme consumes one initial Bell state (wiggly line in the figure) as an entanglement resource between the partitions A and B and requires two-way classical communication visualized by the dashed arrows. The measurements are performed in the computational basis with the outcomes k,l∈{0,1}k,l\in\{0,1\}. Here, HH is the Hadamard gate and ZZ and XX are the Pauli operators.

When employing the teleportation scheme for nn CNOT gates together with a joint quasi-probability decomposition of the nn Bell states, the γ\gamma parameter behaves sub-multiplicatively reducing from O(3n)O(3^n) to O(2n)O(2^n).

When attempting to achieve a similar reduction for joint cutting of two-qubit rotation gates, we encounter the following difficulty: A decomposition of a two-qubit rotation gate based on the teleportation scheme would be sub-optimal since it always consumes one Bell state resulting in γ=3\gamma=3 while the γ\gamma parameter of a two-qubit rotation gate in Eq. (4) is smaller for most values of θ\theta. On the other hand, a deterministic gate teleportation protocol consuming less than one ebit does not exist [32, 33] but only probabilistic implementations [34, 35, 36], which would lead to suboptimal sampling overhead. As a result, a naive generalization of Ref. [23] is impossible.

Single gate instance

In the following, we introduce the alternative scheme depicted in Figure 3 for which we prepare the initial state ∣Ψkl⟩\lvert\Psi_{kl}\rangle, to be specified below, on the ancilla qubits. As a first step, we choose the initial state

Figure 3. Virtual gate teleportation. As explained in the main text, for the state shown in Eq. (6), the correct gate is only teleported for the measurement results k=lk=l, resulting in suboptimal sampling overhead when discarding other outcomes. Since we are only interested in a teleportation scheme together with a quasi-probability simulation of the initial state, we show that in this case, the result k≠lk\ne l can be corrected in the final classical post-processing step. This effectively corresponds to the preparation of the initial state ∣Ψkl⟩\lvert\Psi_{kl}\rangle defined in Eq. (12), which depends on the outcome of the measurement performed later in time, therefore the term virtual teleportation. In the figure, SS is the phase gate.

∣Ψ⟩=cos⁡(θ/2)∣00⟩+sin⁡(θ/2)∣11⟩.(6)\lvert\Psi\rangle=\cos(\theta/2)\lvert00\rangle+\sin(\theta/2)\lvert11\rangle. \tag*{(6)}

As we detail in Appendix § 1.1.1, an optimal QPD of a pure-state density matrix can be readily calculated based on the robustness of entanglement measure [23, 37]. The γ\gamma parameter is calculated as

γ=2(∑jcj)2−1(7)\gamma=2\left(\sum_j c_j\right)^2-1 \tag*{(7)}

where cjc_j are the Schmidt-coefficients of the state. Consequently, for the state shown in Eq. (6), we obtain γ=2(∣cos⁡(θ/2)∣+∣sin⁡(θ/2)∣)2−1\gamma=2(\lvert\cos(\theta/2)\rvert+\lvert\sin(\theta/2)\rvert)^2-1 matching Eq. (4). However, it is straightforward to convince ourselves that the correct gate is teleported only for k=lk=l, and its Hermitian conjugate for k≠lk\ne l [35]. On the one hand, local operators on the partitions AA and BB conditioned on the measurement results to achieve a deterministic protocol do not exist [32, 33]. On the other hand, a repeat-until-success version that is disregarding all measurement outcomes with k≠lk\ne l would lead to the suboptimal sampling overhead 4γ24\gamma^2. Note, however, that we are not interested in deriving an actual deterministic gate teleportation protocol but in a QPD to simulate the two-qubit rotation gate with optimal sampling overhead.

In Appendix § 1.1.1, we derive an alternative optimal QPD for a pure-state density matrix compared to the one presented in Ref. [37]. Applied to Eq. (6), we find

∣Ψ⟩⟨Ψ∣=cos⁡2(θ/2)∣00⟩⟨00∣+sin⁡2(θ/2)∣11⟩⟨11∣(8)\lvert\Psi\rangle\langle\Psi\rvert=\cos^2(\theta/2)\lvert00\rangle\langle00\rvert+\sin^2(\theta/2)\lvert11\rangle\langle11\rvert \tag*{(8)}
+sin⁡(θ)(σ+−σ−).(9)+\sin(\theta)(\sigma^+-\sigma^-). \tag*{(9)}

The explicit form of the separable states σ+\sigma^+ and σ−\sigma^- is specified in Appendix § 1.1.1. To see that the decomposition is optimal, we sum over the absolute of the prefactors, finding again Eq. (4). The states σ+\sigma^+ and σ−\sigma^- are independent of θ\theta, which is the crucial property to perform our protocol as described in the following: As mentioned above, for k≠lk\ne l, the Hermitian conjugate of the two-qubit rotation gate is teleported, which is equivalent to θ→−θ\theta\to-\theta in Eq. (8) and Eq. (9). Because sin⁡(−θ)=−sin⁡(θ)\sin(-\theta)=-\sin(\theta), we could equally choose a minus sign in front of Eq. (9), keep results with k≠lk\ne l, and disregard results with k=lk=l. To make use of both situations, we define the QPD

∣Ψkl⟩⟨Ψkl∣=cos⁡2(θ/2)∣00⟩⟨00∣+sin⁡2(θ/2)∣11⟩⟨11∣(10)\lvert\Psi_{kl}\rangle\langle\Psi_{kl}\rvert=\cos^2(\theta/2)\lvert00\rangle\langle00\rvert+\sin^2(\theta/2)\lvert11\rangle\langle11\rvert \tag*{(10)}
+(−1)k+lsin⁡(θ)(σ+−σ−)(11)+(-1)^{k+l}\sin(\theta)(\sigma^+-\sigma^-) \tag*{(11)}

in which the signs of the quasi-probabilities depend on the measurement outcomes in the form of the factor (−1)k+l(-1)^{k+l}. To execute the protocol, we proceed as detailed in the following: To estimate an expectation value experimentally, one typically defines a post-processing function f(s)∈[−1,1]f(s)\in[-1,1] [14] as a function of the bitstring ss observed at each experimental run and then takes the sample mean over many runs. As explained in the introduction, we perform Monte-Carlo sampling as, for example, explained in Ref. [24]. For each run, we prepare one of the states in Eq. (10) and Eq. (11) sampled according to the probability given by the absolute of the prefactor divided by γ\gamma. In case we initialize the ancilla qubits with one of the states constituting σ+\sigma^+ or σ−\sigma^-, we accumulate ±(−1)k+lγf(s)\pm(-1)^{k+l}\gamma f(s) in the sample mean where the sign depends on the outcome of the measurement on the ancilla qubits. We will refer to our protocol as virtual gate teleportation since an actual entanglement resource state is not physically prepared but only simulated by a quasi-probability decomposition. In this respect, the protocol effectively makes use of the state

∣Ψkl⟩=cos⁡(θ/2)∣00⟩+(−1)k+lsin⁡(θ/2)∣11⟩(12)\lvert\Psi_{kl}\rangle=\cos(\theta/2)\lvert00\rangle+(-1)^{k+l}\sin(\theta/2)\lvert11\rangle \tag*{(12)}

which depends on the outcomes of the measurement performed later in time.

Joint cutting of multiple gates

In this subsection, we generalize the virtual protocol to the joint cutting of nn two-qubit rotation gates at arbitrary positions in the circuit. When cutting nn gate instances independently, the overall γ\gamma parameter defined here as γind.(n)\gamma_{\mathrm{ind.}}^{(n)} behaves multiplicatively, that is

γind.(n)=∏s=1n(1+2∣sin⁡(θs)∣)(13)\gamma_{\mathrm{ind.}}^{(n)} = \prod_{s=1}^{n} (1 + 2\lvert\sin(\theta_s)\rvert) \tag*{(13)}

where we used Eq. (4). In order to investigate if joint decomposition can be done more efficiently, the single-instance virtual teleportation protocol is generalized in the following to nn gates as shown in Figure 4. In the figure we view the nn two-qubit states ∣Ψksls⟩\lvert\Psi_{k_s l_s}\rangle for s=1,…,ns = 1, \ldots, n on the ancilla qubits as a 2n2n-qubit state ∣Ψk1l1…knln⟩\lvert\Psi_{k_1l_1\ldots k_nl_n}\rangle. Again, a specific choice of ksk_s, lsl_s for s=1,…,ns = 1, \ldots, n defining the resource state only translates into the signs of the quasi probabilities of its QPD. In turn, we can choose ks=ls=0k_s = l_s = 0 for all ss of the resource state but correct unwanted measurement results in the post-processing step.

Figure 4. Generalization of the virtual teleportation protocol from the single gate instance shown in Figure 3 to nn two-qubit rotation gates. Each gate requires one ancilla qubit per partition on which we effectively prepare the states ∣Ψksls⟩\lvert\Psi_{k_s l_s}\rangle for s=1,…,ns = 1, \ldots, n by a quasi-probability decomposition. The result of the measurements on the ancilla qubits determines the sign of the quasi-probabilities in the classical post-processing step.

Using Eq. (12) and the qubit arrangement as shown in Figure 4, we find

∣Ψk1l1…knln⟩=∑j∈{0,1}ncj∣j1…jn⟩∣jn…j1⟩(14)\lvert\Psi_{k_1l_1\ldots k_nl_n}\rangle= \sum_{j\in\{0,1\}^{n}} c_j\lvert j_1\ldots j_n\rangle\lvert j_n\ldots j_1\rangle \tag*{(14)}

with cj=∏s=1ncjsc_j = \prod_{s=1}^{n} c_{j_s} and

cjs={cos⁡(θs/2)for js=0(−1)ks+lssin⁡(θs/2)for js=1(15)c_{j_s} = \begin{cases} \cos(\theta_s/2) & \text{for } j_s = 0 \\ (-1)^{k_s+l_s}\sin(\theta_s/2) & \text{for } j_s = 1 \end{cases} \tag*{(15)}

In Eq. (14), the first (second) ket describes the state on the ancilla qubits of partition AA (BB). If we redefine, e.g., the first ket on the right-hand side of Eq. (14) by absorbing the sign of cjc_j, this equation is the Schmidt decomposition of ∣Ψk1l1…knln⟩\lvert\Psi_{k_1l_1\ldots k_nl_n}\rangle allowing us to calculate γjoint(n)\gamma_{\mathrm{joint}}^{(n)} for the QPD as

γjoint(n)=2(∑j∈{0,1}n∣cj∣)2−1(16)\gamma_{\mathrm{joint}}^{(n)} = 2\left(\sum_{j\in\{0,1\}^{n}}\lvert c_j\rvert\right)^2 - 1 \tag*{(16)}
=2∏s=1n(1+∣sin⁡(θs)∣)−1(17)= 2\prod_{s=1}^{n}(1+\lvert\sin(\theta_s)\rvert)-1 \tag*{(17)}
<γind.(n).(18)< \gamma_{\mathrm{ind.}}^{(n)}. \tag*{(18)}

In Appendix § 1.1.1, we explicitly state an optimal quasi-probability decomposition for any pure-state density matrix. Applied to Eq. (14), the measurement-dependent signs in Eq. (15) only appear as the signs of the quasi probabilities, again allowing correction in the classical post-processing step. The γ\gamma parameter in Eq. (17), is, in general, significantly smaller than the γ\gamma parameter for independent cuts. Therefore, we have shown that there exists a decomposition for multiple instances of two-qubit rotation gates with sub-multiplicative behavior of the γ\gamma parameter. In Appendix § 1.1.2, we prove that γjoint(n)\gamma_{\mathrm{joint}}^{(n)} also is a lower bound for the optimal decomposition of nn two-qubit rotation gates. Consequently, joint optimal virtual gate teleportation also translates into optimality of the gate decomposition.

Note that no classical communication is required between the partitions [38]. Joint gate cutting without the need for classical communication significantly alleviates implementation on current hardware for two reasons. First, no real-time feedback for local operations conditioned on measurement results is needed, distinct from conventional gate teleportation protocols as, for example, shown in Figure 2. Second, if all gates connecting the two partitions are cut, the severed sub-circuits can be executed sequentially on the same hardware. Indeed, given a decomposition as in Eq. (1), we first determine the number of shots NN required to achieve a certain accuracy of the expectation value estimate with high probability. Next, we determine how many times the circuit with channel Fi\mathcal{F}_i needs to be executed by sampling NN times from the probability distribution with pi=∣ai∣/κp_i=\lvert a_i\rvert/\kappa and counting the number of times ii is realized. If the decomposition does not require classical communication, Fi=FiA⊗FiB\mathcal{F}_i=\mathcal{F}_i^A\otimes\mathcal{F}_i^B and if Fi\mathcal{F}_i on one partition involves measurements, the Fi\mathcal{F}_i channel on the other partition is independent of the measurement result. If all gates connecting the two partitions are cut, the circuits can be evaluated sequentially and independently from each other since FiA\mathcal{F}_i^A and FiB\mathcal{F}_i^B are completely independent. After all circuits have been executed, the bitstrings that were measured on both partitions for the iith channel are concatenated and passed to the post-processing function. This procedure stands in stark contrast to protocols employing two-way classical communications where two quantum devices connected by classical links must operate in parallel. This results from the structure of Fi\mathcal{F}_i when allowing classical communication. Here, we allow operations that may depend on the outcome of a measurement on the other partition. Since measurement results are probabilistic, the number of times each channel has to be applied cannot be calculated prior to the experiment.

Lastly, we mention again that our protocol contains the joint cutting of nn CNOT gates as a special case with optimal γjoint(n)=2n+1−1\gamma_{\mathrm{joint}}^{(n)} = 2^{n+1} - 1 [23].

Multi-qubit rotation gates

Finally, we consider multi-qubit ZZ rotation gates. A multi-qubit rotation gate can be written as a two-qubit rotation gate sandwiched by ladders of CNOT gates [39] as shown in Figure 5. The task of cutting a multi-qubit ZZ rotation gate then reduces to the cutting of a two-qubit rotation gate. The resulting decomposition is optimal. This can be seen by noting that if the γ\gamma parameter of the multi-qubit rotation gate was smaller than that of a two-qubit rotation gate, we could use the former to construct a decomposition of the latter with smaller γ\gamma, leading to a contradiction.

Figure 5. A multi-qubit rotation gate is equivalent to a two-qubit rotation gate up to local operations (with respect to the two-partitions AA and BB). Consequently, the γ\gamma parameter of this gate equals the one of the two-qubit rotation gate.

Parallel gates can be cut without ancilla qubits

Interestingly, as we will show in the following, there is an ancilla-free joint decomposition of parallel gates. With parallel gates, we refer to gates that can be executed at the same time slice of the circuit, for example, as shown in Figure 1 for the case of CNOT gates. In Appendix § 1.1.3, we start from the protocol in Figure 4 and subsequently show that it can be reduced to an ancilla-free decomposition in terms of local operations on the partition AA and BB. Remarkably, again, no classical communication between the partitions is required, and optimality is preserved. The explicit formula for the decomposition is shown in Eq. (43). It contains single-qubit ZZ gates, as well as multi-qubit operations on all subsets of the nn qubits on each partition AA and BB. The operations consist of two different types. The first are multi-qubit rotation gates by angles ±π/2\pm\pi/2. They can be implemented by single-qubit rotation gates sandwiched by ladders of CNOT gates [39]. The second are non-unitary operations, where the single-qubit rotation gates within the CNOT ladders are replaced by computational-basis measurements; see a detailed discussion in Appendix § 1.1.3. As a consequence, each term in the decomposition can be implemented with O(n)O(n) CNOT gates. Note that an nn qubit rotation gate about ±π/2\pm\pi/2 can be implemented with exactly nn CNOT gates.

CNOT gates. Because of that and since the majority of terms in the decomposition of an nn-qubit rotation gate shown in Eq. (43) contain operations on less than nn qubits, we expect strong noise reduction by using our scheme. Noise mitigation due to the reduction of costly two-qubit gates in circuit-cutting schemes was recently observed experimentally in Ref. [24].

It has been emphasised that the sampling overhead is not the only relevant metric measuring the quality of a circuit-cutting scheme [16] but also the number LL of different channels to be applied. In principle, the number of experimental shots required to evaluate an expectation value to additive error ϵ\epsilon scales as O(γ2/ϵ2)O(\gamma^2/\epsilon^2) which is independent of LL. In practice, however, the latency introduced by the additional compilation time needed for each of the LL sub-circuits corresponding to the elements Fi\mathcal{F}_i for i=1,…,Li = 1, \ldots, L on topologically constrained hardware can be the dominant factor in the runtime of the algorithm [16]. As discussed in Appendix § 1.1.1, our decomposition guarantees L=O(4n)L = O(4^n) for the case of parallel as well as non-parallel gates, which is an exponential improvement over previous results. It should be noted that we could trade compilation time versus additional circuit depth. Indeed, a multi-qubit rotation gate can be trivially routed to topologically constrained hardware by SWAP insertion. This decreases compilation latency to almost zero but, in turn, might drastically increase the CNOT-gate count and the additional circuit depth dd, resulting in a more severe impact of noise. Note that a multi-qubit rotation gate can be implemented on fully connected hardware with depth d=O(log⁡(n))d = O(\log(n)) when replacing each CNOT gate ladder by a balanced tree [39]. For hardware with constrained connections, efficient compilation methods exist for multi-qubit rotation gates based on minimum spanning trees [40] and CNOT gate re-synthesis [41]. In what sense the low depth of the circuits can be retained will be the focus of further investigations.

Conclusion

In this work, we introduced joint cutting of non-Clifford two-qubit rotation gates based on virtual teleportation and proved optimality. In the case of parallel gates, we further derived an ancilla-free optimal decomposition. We conclude by stressing the following aspects: As mentioned before, controlled rotation gates are equivalent to two-qubit rotation gates up to local unitary operations. In addition, CNOT gates are special instances of this gate class. Consequently, the joint virtual teleportation protocol proposed in this work can also be used for optimal joint cutting of CNOT gates with several improvements over previous work [23]. (1) In our virtual teleportation protocol, no classical communication needs to be shared. As a result, no real-time feedback during the quantum computation in the form of local correction operations conditioned on the measurement outcomes on the ancilla qubits is required. (2) As a consequence, the cut circuits can be run in sequence on the same hardware as opposed to parallel execution, which was necessary for previous methods. (3) By our alternative quasi-probability decomposition of pure-state density matrices, we reach an exponential reduction of the number of terms required compared to Refs. [23, 37], directly translating into an exponential reduction of the number of channels in the cutting scheme. (4) Our decomposition method allows us to derive ancilla-free optimal joint cutting schemes for CNOT gates, two-qubit rotation gates, and controlled rotation gates, which has not yet been considered in the literature.

After completion of our manuscript, Refs. [42, 43] appeared as preprints which generalize some of our ideas.

Acknowledgments

C.U. would like to thank M. Bechtold, D. Sutter, and F. Wagner for helpful discussions. The research was funded by the project QuaST, supported by the Federal Ministry for Economic Affairs and Climate Action on the basis of a decision by the German Bundestag.

Optimal QPD for a pure-state density matrix

In this appendix, we derive an alternative optimal QPD for arbitrary pure-state density matrices. In Ref. [37], Vidal and Tarrach consider the following problem: Given two partitions and a bipartite state ρ\rho. What is the minimal mixing of the state with a separable state such that the mixed state becomes separable as well? This problem can be rephrased as follows [23]: What is the minimal RR, called robustness of entanglement, for which

ρ=(1+R)η1−Rη2(19)\rho= (1+R)\eta_1 - R\eta_2 \tag*{(19)}

where η1\eta_1 and η2\eta_2 are separable. While such decomposition is hard to find in general, for a pure state ρ=∣ψ⟩⟨ψ∣\rho= |\psi\rangle\langle\psi| the robustness can be calculated via the mm Schmidt coefficients cjc_j with j=0,…,m−1j = 0,\ldots,m-1 of the ∣ψ⟩|\psi\rangle state as

R=(∑j=0m−1cj)2−1.(20)R = \left(\sum_{j=0}^{m-1} c_j\right)^2 - 1. \tag*{(20)}

Consequently,

γ=1+2R.(21)\gamma= 1 + 2R. \tag*{(21)}

In Ref. [37], the authors also provide an explicit representation for η1\eta_1 and η2\eta_2 in which, however, the separable states themselves are functions of the Schmidt coefficients. In contrast, the alternative QPD derived in the following only contains the Schmidt coefficients in the quasi-probabilities. As discussed in the main text, this guarantees that, when applied to the protocol in Figure 3 and Figure 4, we can correct the unwanted measurement results in the classical post-processing step. A similar representation has been derived in Refs. [44, 45]. In the following, we first derive the general form of the decomposition and subsequently show optimality: Consider a bipartite state ∣ψ⟩|\psi\rangle on the partitions AA and BB and an expansion of the form

∣ψ⟩=∑j=0m−1cj∣φj⟩⊗∣φj′⟩(22)|\psi\rangle= \sum_{j=0}^{m-1} c_j|\varphi_j\rangle\otimes|\varphi'_j\rangle \tag*{(22)}

with cjc_j real but not necessarily positive. Then

∣ψ⟩⟨ψ∣=∑j=0m−1cj2∣φj⟩⟨φj∣⊗∣φj′⟩⟨φj′∣+2∑i>jcicj(σij+−σij−)(23)|\psi\rangle\langle\psi| = \sum_{j=0}^{m-1} c_j^2|\varphi_j\rangle\langle\varphi_j| \otimes|\varphi'_j\rangle\langle\varphi'_j| + 2\sum_{i>j}c_i c_j\left(\sigma_{ij}^{+}-\sigma_{ij}^{-}\right) \tag*{(23)}

holds. In this expression

σij±=1α∑r=1α∣ξrij±⟩⟨ξrij±∣⊗∣τrij⟩⟨τrij∣.(24)\sigma_{ij}^{\pm} = \frac{1}{\alpha}\sum_{r=1}^{\alpha}|\xi_{rij}^{\pm}\rangle\langle\xi_{rij}^{\pm}| \otimes|\tau_{rij}\rangle\langle\tau_{rij}|. \tag*{(24)}

are separable density matrices with respect to the partitions AA and BB. The states take the form

∣ξrij±⟩=12(∣φi⟩±eiϕr∣φj⟩)(25)|\xi_{rij}^{\pm}\rangle= \frac{1}{\sqrt{2}}\left(|\varphi_i\rangle\pm e^{i\phi_r}|\varphi_j\rangle\right) \tag*{(25)}

and

∣τrij⟩=12(∣φi′⟩+e−iϕr∣φj′⟩).(26)|\tau_{rij}\rangle= \frac{1}{\sqrt{2}}\left(|\varphi'_i\rangle+ e^{-i\phi_r}|\varphi'_j\rangle\right). \tag*{(26)}

Finally, the phases ϕr\phi_r can be chosen such that

∑r=1αeiϕr−∑r=1αei2ϕr=0.(27)\sum_{r=1}^{\alpha}e^{i\phi_r}-\sum_{r=1}^{\alpha}e^{i2\phi_r}=0. \tag*{(27)}

Furthermore, if Eq. (A4) is the Schmidt decomposition of ∣ψ⟩|\psi\rangle—in this case cj≥0c_j \ge0—then Eq. (A5) is optimal in that it achieves the minimal possible γ\gamma.

Proof. The statement is most easily proven by substituting Eqs. (A6)–(A9) into Eq. (A5). It remains to show optimality in case Eq. (A4) is the Schmidt decomposition of ∣ψ⟩|\psi\rangle. To this end, we sum over the absolute of the coefficients for all terms with the result stated in Eq. (A2) and Eq. (A3). Therefore, the decomposition is optimal.

We choose ϕr=2πr/α\phi_r = 2\pi r/\alpha for integer α≥3\alpha\ge3. The choice α=3\alpha= 3 involves the least amount of terms, but we observe in Appendix C that α=4\alpha= 4 allows removing ancilla qubits for parallel gates. Eq. (A5) involves O(m2)O(m^2) terms. This is an exponential improvement to the decomposition used in Ref. [37] with O(2m)O(2^m) terms.

Lower bounds

In this appendix we prove a lower bound on γjoint(n)\gamma_{\mathrm{joint}}^{(n)}, the γ\gamma parameter for jointly cutting nn two-qubit rotation gates. This bound will agree with the upper bound established in Eq. (17) by the joint virtual teleportation scheme, thereby proving optimality. A lower bound on the γ\gamma parameter of a quantum gate can be obtained from the QPD of the Choi state of the gate’s unitary [23]. The argument is the following: Since the Choi state of a gate’s unitary can be formed by local (with respect to the partitions AA and BB) operations, the γ\gamma parameter of the gate cannot possibly be smaller than that of the Choi state. If it were, construction of the Choi state with smaller γ\gamma would be possible, leading to a contradiction. Thus, Eq. (7) provides

γ≥2(∑jcj)2−1(28)\gamma\ge2\left(\sum_j c_j\right)^2-1 \tag*{(28)}

where cjc_j are the Schmidt coefficients of the Choi state of the gate. Further note that the Choi state of a gate whose matrix representation is diagonal in the computational basis has the same Schmidt coefficients as the normalized vector containing the diagonal elements. In our case, this vector is just ∣Ψk1l1…knln⟩\lvert\Psi_{k_1l_1\ldots k_nl_n}\rangle for ks=ls=0k_s=l_s=0 for all ss up to local operations. Consequently, the lower bound matches the upper, proving the optimality of the joint virtual teleportation approach for joint cutting of two-qubit rotation gates.

Ref. [23] proved optimality for a large class of gate decomposition derived in Ref. [22]. Note, however, that the lower bound obtained in this way can be relatively loose for some gates. E.g., in case of a KK-qubit version of a Toffoli gate, it can be shown that the right-hand side of Eq. (28) for a cut after one qubit tends to one as K→∞K\to\infty. Since, however, this gate can be used to create a Bell state between two partitions, γ≥3\gamma\ge3 must be true.

Parallel gates

In this appendix, we derive the ancilla-free decomposition of nn parallel two-qubit rotation gates for which we start from the protocol in Figure 4. First, we define the map

Λ(∣ψ⟩⟨ψ∣)[⋅]=2n∑i,j⟨i∣ψ⟩⟨ψ∣j⟩Pi⋅Pj(29)\Lambda(\lvert\psi\rangle\langle\psi\rvert)[\cdot]=2^n\sum_{i,j}\langle i\vert\psi\rangle\langle\psi\vert j\rangle P_i\cdot P_j \tag*{(29)}

where Pi=∣i⟩⟨i∣P_i=\lvert i\rangle\langle i\rvert and {∣i⟩}i=02n−1\{\lvert i\rangle\}_{i=0}^{2^n-1} is the computational basis. This map corresponds to the transformation U⋅U†U\cdot U^\dagger where UU contains the computational basis elements of ∣ψ⟩\lvert\psi\rangle multiplied by 2n\sqrt{2^n} on its diagonal. Thus, UU is unitary if ∣⟨i∣ψ⟩∣=1/2n\lvert\langle i\vert\psi\rangle\rvert=1/\sqrt{2^n} for all ii. Further, note that Λ\Lambda is linear in its first argument, and if ∣ψ⟩\lvert\psi\rangle factorizes over two partitions, then the map does as well.

Let us define as Rzz(n)\mathcal{R}_{zz}^{(n)} the 2n2n-qubit unitary channel corresponding to the nn two-qubit rotation gates we want to cut and a state ∣ψ⟩\lvert\psi\rangle such that

Λ(∣ψ⟩⟨ψ∣)[⋅]=Rzz(n).(30)\Lambda(\lvert\psi\rangle\langle\psi\rvert)[\cdot]=\mathcal{R}_{zz}^{(n)}. \tag*{(30)}

With the Hadamard gate HH and the phase gate SS this state is

∣ψ⟩=H⊗n⊗(HS†)⊗n∣Ψ⟩(31)\lvert\psi\rangle=H^{\otimes n}\otimes(HS^\dagger)^{\otimes n}\lvert\Psi\rangle \tag*{(31)}

with ∣Ψ⟩\lvert\Psi\rangle as in Eq. (14) but with ks=ls=0k_s=l_s=0 for all ss, that is

∣Ψ⟩=∑j∈{0,1}ncj∣j1…jn⟩∣jn…j1⟩(32)\lvert\Psi\rangle=\sum_{j\in\{0,1\}^n}c_j\lvert j_1\ldots j_n\rangle\lvert j_n\ldots j_1\rangle \tag*{(32)}

with cj=∏s=1ncjsc_j=\prod_{s=1}^n c_{j_s} and

cjs={cos⁡(θs/2)for js=0sin⁡(θs/2)for js=1(33)c_{j_s}= \begin{cases} \cos(\theta_s/2) & \text{for }j_s=0\\ \sin(\theta_s/2) & \text{for }j_s=1 \end{cases} \tag*{(33)}

It is left to insert a QPD of ∣ψ⟩⟨ψ∣\lvert\psi\rangle\langle\psi\rvert calculated with Appendix A into Eq. (29) and then use linearity and factorization properties of Λ\Lambda. Comparison with Eq. (22) shows m=2nm=2^n, ∣φj⟩=∣j1,…,jn⟩\lvert\varphi_j\rangle=\lvert j_1,\ldots,j_n\rangle, and ∣φj′⟩=(HS†)⊗n∣jn,…,j1⟩\lvert\varphi'_j\rangle=(HS^\dagger)^{\otimes n}\lvert j_n,\ldots,j_1\rangle. To calculate the map Λ\Lambda, we first make use of linearity and calculate the different terms individually. When we define the unitary channel

Zj[⋅]=Zj1⊗⋯⊗Zjn⋅Zj1⊗⋯⊗Zjn(34)\mathcal{Z}_j[\cdot]=Z^{j_1}\otimes\cdots\otimes Z^{j_n}\cdot Z^{j_1}\otimes\cdots\otimes Z^{j_n} \tag*{(34)}

corresponding to the application of single qubit ZZ gates, we find

Λ(∣φj⟩⟨φj∣)[⋅]=Zj[⋅](35)\Lambda(\lvert\varphi_j\rangle\langle\varphi_j\rvert)[\cdot]=\mathcal{Z}_j[\cdot] \tag*{(35)}

where we used

2∑ks∈{0,1}⟨ks∣H∣js⟩Pks=∑ks∈{0,1}(−1)jsksPks=Zjs.(36)\sqrt{2}\sum_{k_s\in\{0,1\}}\langle k_s\vert H\vert j_s\rangle P_{k_s}=\sum_{k_s\in\{0,1\}}(-1)^{j_sk_s}P_{k_s}=Z^{j_s}. \tag*{(36)}

Equally, we find the same result for ∣φj′⟩\lvert\varphi'_j\rangle for j~:=(jn,…,j1)\tilde{j}:=(j_n,\ldots,j_1). The evaluation of the states ∣ξrij±⟩\lvert\xi_{r_{ij}}^\pm\rangle and ∣τrij⟩\lvert\tau_{r_{ij}}\rangle requires a little bit more work. First, we insert ∣ξrij±⟩\lvert\xi_{r_{ij}}^\pm\rangle, defined in Eq. (25), with the result

2n∑k⟨k∣ξrij±⟩Pk=Zi1⊗⋯⊗Zin⊗[(I⊗n±eiϕrZj1−i1⊗⋯⊗Zjn−in)/2].(37)\sqrt{2^n}\sum_k\langle k\vert\xi_{r_{ij}}^\pm\rangle P_k=Z^{i_1}\otimes\cdots\otimes Z^{i_n}\otimes\left[(\mathbb{I}^{\otimes n}\pm e^{i\phi_r}Z^{j_1-i_1}\otimes\cdots\otimes Z^{j_n-i_n})/\sqrt{2}\right]. \tag*{(37)}

For ϕr=2πr/α\phi_r=2\pi r/\alpha with α=4\alpha=4, we first consider exp⁡(iϕ1)=i\exp(i\phi_1)=i and exp⁡(iϕ3)=−i\exp(i\phi_3)=-i. In this case, the expression in the brackets is unitary. Indeed,

Rij(±π/2)=I⊗n±iZj1−i1⊗⋯⊗Zjn−in2(38)R_{ij}(\pm\pi/2)=\frac{\mathbb{I}^{\otimes n}\pm iZ^{j_1-i_1}\otimes\cdots\otimes Z^{j_n-i_n}}{\sqrt{2}} \tag*{(38)}

is a multi-qubit rotation gate on the qubits with ∣is−js∣=1\lvert i_s-j_s\rvert=1. Again, we define the corresponding channel Rij(±π/2)R_{ij}(\pm\pi/2) using calligraphic notation. Furthermore, we introduce the abbreviation

Rij=Rij(π/2)−Rij(−π/2)2(39)\mathcal{R}_{ij}=\frac{\mathcal{R}_{ij}(\pi/2)-\mathcal{R}_{ij}(-\pi/2)}{2} \tag*{(39)}

of the unitary channels. We now turn to Eq. (37) with exp⁡(iϕ2)=−1\exp(i\phi_2)=-1 and exp⁡(iϕ4)=1\exp(i\phi_4)=1. In this case, we define

Pijk=I⊗n+(−1)kZj1−i1⊗⋯⊗Zjn−in2(40)P_{ij}^k=\frac{\mathbb{I}^{\otimes n}+(-1)^kZ^{j_1-i_1}\otimes\cdots\otimes Z^{j_n-i_n}}{2} \tag*{(40)}

for k=0,1k=0,1, which is non-unitary. The channel Pijk\mathcal{P}_{ij}^k can be evaluated on a quantum computer using a ladder of CNOT gates [46] and a projector on ∣0⟩\lvert0\rangle or ∣1⟩\lvert1\rangle, e.g.

I⊗t+(−1)kZ⊗t2\frac{\mathbb{I}^{\otimes t}+(-1)^kZ^{\otimes t}}{2}

Figure C13.

for integer t>0t>0. We then define

Pij=Pij0−Pij1(41)\mathcal{P}_{ij}=\mathcal{P}_{ij}^0-\mathcal{P}_{ij}^1 \tag*{(41)}

which is neither trace-preserving nor positive. However, Pij\mathcal{P}_{ij} is the difference of two completely positive trace non-increasing (CPTN) maps, whose sum is completely positive and trace preserving (CPTP). Such maps can be simulated on a quantum device without extra sampling overhead [21, 22, 23, 24]. Thus, both Rij\mathcal{R}_{ij} and Pij\mathcal{P}_{ij} can be simulated with γ=1\gamma=1. The evaluation of Eq. (29) for ∣τrij⟩\lvert\tau_{rij}\rangle proceeds along the same lines. We only need to replace i,j→i~,j~i,j\to\tilde{i},\tilde{j}, choose the plus sign in Eq. (37), and

replace ϕr→−ϕr\phi_r\to-\phi_r. Due to the extra S†S^\dagger gate in the definition of ∣φ′⟩\lvert\varphi'\rangle, we additionally have to replace Z→−iZZ\to-iZ, introducing a factor (−i)νij(-i)^{\nu_{ij}} with

νij=∑s=1n(js−is).(42)\nu_{ij}=\sum_{s=1}^{n}(j_s-i_s). \tag*{(42)}

Collecting all the terms, we finally arrive at

Rzz(n)=∑j∈{0,1}ncj2Zj⊗Z~j+2∑i>jcicj[Zi⊗Z~i]∘{(−1)νij/2[Pij⊗P~ij−Rij⊗R~ij]for νij even(−1)(νij−1)/2[Rij⊗P~ij+Pij⊗R~ij]for νij odd(43)\mathcal{R}_{zz}^{(n)}=\sum_{j\in\{0,1\}^{n}}c_j^2 Z_j\otimes\widetilde{Z}_j+2\sum_{i>j}c_i c_j[Z_i\otimes\widetilde{Z}_i]\circ\begin{cases}(-1)^{\nu_{ij}/2}\left[\mathcal{P}_{ij}\otimes\widetilde{\mathcal{P}}_{ij}-\mathcal{R}_{ij}\otimes\widetilde{\mathcal{R}}_{ij}\right]&\text{for }\nu_{ij}\text{ even}\\(-1)^{(\nu_{ij}-1)/2}\left[\mathcal{R}_{ij}\otimes\widetilde{\mathcal{P}}_{ij}+\mathcal{P}_{ij}\otimes\widetilde{\mathcal{R}}_{ij}\right]&\text{for }\nu_{ij}\text{ odd}\end{cases} \tag*{(43)}

This decomposition is optimal with

γ=2∏s=1n(1+∣sin⁡(θs)∣)−1.(44)\gamma=2\prod_{s=1}^{n}(1+\lvert\sin(\theta_s)\rvert)-1. \tag*{(44)}

It consists of single-qubit ZZ gates, multi-qubit ZZ rotations by the angles ±π/2\pm\pi/2 and measurements within CNOT-gate ladders. Due to the double sum, the number of terms in Eq. (43) grows as O(4n)O(4^n). Interestingly, the decomposition achieves the optimal γ\gamma parameter even though no exchange of classical information is required between the partitions.

References

References

  1. [1]P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE Comput. Soc. Press, 1994) p. 124.
  2. [2]L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, New York, NY, USA, 1996) p. 212.arxiv.org/abs/quant-ph/9605043
  3. [3]M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, D. Eppens, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, A. Ho, S. Hong, T. Huang, L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P. V. Klimov, A. N. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, M. Lindmark, M. Leib, O. Martin, J. M. Martinis, J. R. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, M. Wruckiewicz, J. Mutus, O. Naaman, C. Neill, F. Neukart, M. Y. Niu, T. E. O’Brien, B. O’Gorman, E. Ostby, A. Petukhov, H. Putterman, C. Quintana, P. Roushan, N. C. Rubin, D. Sank, A. Skolik, V. Smelyanskyi, D. Strain, M. Streif, M. Szalay, A. Vainsencher, T. White, Z. J. Yao, P. Yeh, A. Zalcman, L. Zhou, H. Neven, D. Bacon, E. Lucero, E. Farhi, and R. Babbush, Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nat. Phys. 17, 332 (2021).DOI
  4. [4]E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028.arxiv.org/abs/1411.4028
  5. [5]V. Havlíček, A. D. Córcoles, K. Temme, M. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209 (2019).DOI
  6. [6]J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).DOI
  7. [7]B. P. Lanyon, J. D. Whitfield, G. G. Gillett, M. E. Goggin, M. P. Almeida, I. Kassal, J. D. Biamonte, M. Mohseni, B. J. Powell, M. Barbieri, A. Aspuru-Guzik, and A. G. White, Towards quantum chemistry on a quantum computer, Nat. Chem. 2, 106 (2010).DOI
  8. [8]A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).DOI
  9. [9]Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. van den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zaletel, K. Temme, and A. Kandala, Evidence for the utility of quantum computing before fault tolerance, Nature 618, 500 (2023).DOI
  10. [10]M. H. Devoret and R. J. Schoelkopf, Superconducting circuits for quantum information: An outlook, Science 339, 1169 (2013).DOI
  11. [11]C. Monroe and J. Kim, Scaling the ion trap quantum processor, Science 339, 1164 (2013).DOI
  12. [12]X. Yuan, B. Regula, R. Takagi, and M. Gu, Virtual quantum resource distillation (2023), arXiv:2303.00955.DOI
  13. [13]M. Bechtold, J. Barzen, F. Leymann, and A. Mandl, Circuit cutting with non-maximally entangled states (2023), arXiv:2306.12084.arxiv.org/abs/2306.12084
  14. [14]T. Peng, A. W. Harrow, M. Ozols, and X. Wu, Simulating large quantum circuits on a small quantum computer, Phys. Rev. Lett. 125, 150504 (2020).DOI
  15. [15]L. Brenner, C. Piveteau, and D. Sutter, Optimal wire cutting with classical communication (2023), arXiv:2302.03366.DOI
  16. [16]H. Harada, K. Wada, and N. Yamamoto, Doubly optimal parallel wire cutting without ancilla qubits (2023), arXiv:2303.07340.DOI
  17. [17]A. Lowe, M. Medvidovic, A. Hayes, L. J. O’Riordan, T. R. Bromley, J. M. Arrazola, and N. Killoran, Fast quantum circuit cutting with randomized measurements, Quantum 7, 934 (2023).DOI
  18. [18]G. Uchechara, T. M. Aamodt, O. D. Matteo, Rotation-inspired circuit cut optimization, in 2022 IEEE/ACM Third International Workshop on Quantum Computing Software (QCS) (IEEE Computer Society, Los Alamitos, CA, USA, 2022) p. 50.
  19. [19]P. Pednault, An alternative approach to optimal wire cutting without ancilla qubits (2023), arXiv:2303.08287.arxiv.org/abs/2303.08287
  20. [20]H. F. Hofmann, How to simulate a universal quantum computer using negative probabilities, J. Phys. A: Math. Theor. 42, 275304 (2009).DOI
  21. [21]K. Mitarai and K. Fujii, Constructing a virtual two-qubit gate by sampling single-qubit operations, New J. Phys. 23, 023021 (2021).DOI
  22. [22]K. Mitarai and K. Fujii, Overhead for simulating a non-local channel with local channels by quasiprobability sampling, Quantum 5, 388 (2021).DOI
  23. [23]C. Piveteau and D. Sutter, Circuit knitting with classical communication, IEEE Trans. Inf. Theory 70, 2734 (2024).DOI
  24. [24]C. Ufrecht, M. Periyasamy, S. Rietsch, D. D. Scherer, A. Plinge, and C. Mutschler, Cutting multi-control quantum gates with ZX calculus, Quantum 7, 1147 (2023).DOI
  25. [25]H. Pashayan, J. J. Wallman, and S. D. Bartlett, Estimating outcome probabilities of quantum circuits using quasiprobabilities, Phys. Rev. Lett. 115, 070501 (2015).DOI
  26. [26]C. Piveteau, D. Sutter, and S. Woerner, Quasiprobability decompositions with reduced sampling overhead, npj Quantum Inf. 8, 12 (2022).DOI
  27. [27]K. Temme, S. Bravyi, and J. M. Gambetta, Error mitigation for short-depth quantum circuits, Phys. Rev. Lett. 119, 180509 (2017).DOI
  28. [28]L. S. Herzog, F. Wagner, C. Ufrecht, L. Palackal, A. Plinge, C. Mutschler, and D. D. Scherer, Improving quantum and classical decomposition methods for vehicle routing, arXiv:2404.05551 (2024).arxiv.org/abs/2404.05551
  29. [29]D. Collins, N. Linden, and S. Popescu, Nonlocal content of quantum operations, Phys. Rev. A 64, 032302 (2001).DOI
  30. [30]D. Gottesman and I. L. Chuang, Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations, Nature 402, 390 (1999).DOI
  31. [31]J. Eisert, K. Jacobs, P. Papadopoulos, and M. B. Plenio, Optimal local implementation of nonlocal quantum gates, Phys. Rev. A 62, 052317 (2000).DOI
  32. [32]D. Stahlke and R. B. Griffiths, Entanglement requirements for implementing bipartite unitary operations, Phys. Rev. A 84, 032316 (2011).
  33. [33]A. Soeda, P. S. Turner, and M. Murao, Entanglement cost of implementing controlled-unitary operations, Phys. Rev. Lett. 107, 180501 (2011).pubmed.ncbi.nlm.nih.gov/22107615
  34. [34]J. I. Cirac, W. Dür, B. Kraus, and M. Lewenstein, Entangling operations and their implementation using a small amount of entanglement, Phys. Rev. Lett. 86, 544 (2001).pubmed.ncbi.nlm.nih.gov/11177876
  35. [35]W. Dür and J. I. Cirac, Nonlocal operations: Purification, storage, compression, tomography, and probabilistic implementation, Phys. Rev. A 64, 012317 (2001).DOI
  36. [36]B. Gromada and B. Reznik, Implementing nonlocal gates with nonmaximally entangled states, Phys. Rev. A 71, 032322 (2005).
  37. [37]G. Vidal and R. Tarrach, Robustness of entanglement, Phys. Rev. A 59, 141 (1999).DOI
  38. [38]It can be shown that all operations in the virtual teleportation protocol are elements of the extended definition of local operations used in Ref. [15, 23].
  39. [39]A. Cowtan, S. Dilkes, R. Duncan, W. Simmons, and S. Sivarajah, Phase gadget synthesis for shallow circuits, EPTCS 318, 213 (2020).
  40. [40]S. Gogioso and R. Yeung, Annealing optimisation of mixed ZX phase circuits, in Proceedings 19th International Conference on Quantum Physics and Logic, Wolfson College, Oxford, UK, EPTCS, Vol. 394, edited by S. Gogioso and M. Hoban (2023) pp. 415–431.DOI
  41. [41]B. Nash, V. Gheorghiu, and M. Mosca, Quantum circuit optimizations for nisq architectures, Quantum Sci. Technol. 5, 025010 (2020).DOI
  42. [42]L. Schmitt, C. Piveteau, and D. Sutter, Cutting circuits with multiple two-qubit unitaries (2024), arXiv:2312.11638.DOI
  43. [43]A. W. Harrow and A. Lowe, Optimal quantum circuit cuts with application to clustered Hamiltonian simulation, arXiv:2403.01018 (2024).DOI
  44. [44]J. Sperling and W. Vogel, Representation of entanglement by negative quasiprobabilities, Phys. Rev. A 79, 042337 (2009).DOI
  45. [45]J. Sperling and W. Vogel, Erratum: Representation of entanglement by negative quasiprobabilities [Phys. Rev. A 79, 042337 (2009)], Phys. Rev. A 80, 029905 (2009).
  46. [46]K. Mitarai and K. Fujii, Methodology for replacing indirect measurements with direct measurements, Phys. Rev. Research 1, 013006 (2019).DOI

Paper details

vlnc:W_pr5rw7np
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents