TL;DR
This paper explores "circuit knitting," a technique to simulate large quantum circuits on smaller quantum computers by breaking them into subcircuits. The authors show that allowing classical communication between these subcircuits can significantly reduce the computational overhead compared to methods that rely solely on local operations. This is achieved by leveraging quasiprobability simulation and demonstrating that classical communication can improve the efficiency of simulating multiple nonlocal gates.
What Problem Does This Paper Address?
The primary challenge in building useful quantum computers is the limited number of qubits available. This scarcity hinders the execution of complex quantum algorithms. "Circuit knitting" offers a solution by partitioning a large quantum circuit into smaller, manageable subcircuits that can be processed on smaller quantum devices. However, this partitioning often introduces a "simulation overhead" due to the need to simulate nonlocal gates (gates connecting different subcircuits) using local operations. This overhead can grow exponentially with the number of nonlocal gates. This paper investigates whether introducing classical communication between the subcircuits can mitigate this overhead, making circuit knitting a more practical approach for near-term quantum computers.
Methods
The core of the paper revolves around "quasiprobability simulation." This technique allows for the simulation of nonlocal gates by replacing them with probabilistic combinations of local operations. The efficiency of this method is quantified by the "γ-factor," which represents the sampling overhead. The authors explore three settings:
- Local Operations (LO): Subcircuits are processed independently with no communication.
- Local Operations and One-Way Classical Communication (LOCC): Classical information can be sent from one subcircuit (A) to another (B).
- Local Operations and Two-Way Classical Communication (LOCC): Classical information can be exchanged in both directions between subcircuits.
The paper introduces a novel technique that utilizes "gate teleportation" and the concept of "submultiplicativity" of the γ-factor. By preparing entangled states (like Bell pairs) in parallel and then using them to simulate nonlocal gates via teleportation, the authors demonstrate a significant reduction in the sampling overhead, especially when dealing with multiple instances of the same nonlocal gate. They also analyze the γ-factor for various classes of quantum gates, including Clifford and controlled-rotation gates.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Classical Communication is Beneficial for Circuit Knitting: The most significant insight is that allowing classical communication between subcircuits can indeed reduce the sampling overhead associated with circuit knitting, particularly when simulating multiple nonlocal gates.
- Submultiplicativity of the γ-factor: The paper highlights that the γ-factor is not just submultiplicative but can be strictly submultiplicative under the tensor product for certain states (like Bell pairs). This means preparing multiple entangled states in parallel is more efficient than preparing them sequentially.
- Gate Teleportation as a Key Tool: Gate teleportation, a protocol that uses entanglement to implement a quantum gate, is shown to be a powerful mechanism for reducing the overhead when classical communication is allowed.
- γ-factor Characterization: The paper provides analytical formulas for the γ-factor of various two-qubit gates, offering a precise understanding of their simulation cost under different communication settings.
Key Results
- For simulating a single nonlocal gate, classical communication offers no advantage for many common gates (e.g., CNOT, SWAP, controlled-rotation gates). In these cases, the γ-factor remains the same across LO, LOCC, and LOCC settings.
- When simulating multiple instances of a nonlocal Clifford gate, classical communication (LOCC) can significantly reduce the sampling overhead. For example, simulating $n$ CNOT gates can be reduced from an overhead scaling as $O(9^n)$ to $O(4^n)$.
- The paper derives exact formulas for the γ-factor of several important two-qubit gates, including Clifford gates, controlled-rotation gates, and two-qubit rotations.
- For controlled-rotation gates $CR_x(\theta)$, classical communication can reduce the sampling overhead for certain ranges of $\theta$ ($\pi/3 < \theta < 5\pi/3$).
Limitations and Future Work
- Non-Clifford Gates: While the paper shows improvements for controlled-rotation gates, the generalization of the technique to arbitrary non-Clifford gates remains more complex and less understood. The exact reduction in sampling overhead for these gates is an open question for certain parameter regimes.
- Application Identification: The authors acknowledge that identifying specific useful applications where this circuit knitting framework can demonstrate a quantum advantage is an open problem. Ideally, these applications would involve circuits with a relatively small number of nonlocal gates and where the local computations themselves are challenging for classical computers.
- Memory Overhead: The proposed technique for reducing overhead for multiple instances requires quantum memory to store entangled states. The paper discusses a trade-off between memory footprint and effective sampling overhead, suggesting further research into optimizing this trade-off.
Summary updated