Quantum-Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits

Quantum teleportation transfers and processes quantum information through quantum entanglement channels. It is one of the most versatile protocols in quantum information science and leads to many remarkable applications, particularly the one-way quantum computing. Here, we show, for the first time, that the concept of teleportation can also be used to facilitate an important classical computing task, sampling random quantum circuits, which is highly relevant to prove the near-term demonstration of quantum computational supremacy. In our method, the classical computation in the physical-qubit state space is converted to simulate teleportation in logical-qubit state space, resulting in a much smaller number of qubits involved in classical computing. We tested this new method on 1D and 2D lattices up to 1000 qubits. This Letter presents a new quantum-inspired classical computing technology and is helpful to design and optimize classically hard quantum sampling experiments.

Figure 1

Quantum-teleportation-inspired classical algorithm. (a) The circuit of quantum teleportation. Three physical qubits (black lines) in the quantum circuit are mimicked by one logical qubit (pink line). The logical qubit is used to redirect the flow of quantum information along the circuit topological structure. (b) Classical simulation of low-depth quantum circuits. Logical qubits are defined along the layers of 2-qubit entangling gates. The number of logical qubits is proportional to the circuits depth. For a low-depth circuit, the number of logical qubits can be far less than the physical qubits, therefore providing a memory-efficient classical simulation framework. (c) An example of circuit transformation from physical-qubit unitary circuit to logical-qubit-based nonunitary circuit. Nonunitary circuits can be directly simulated by matrix-vector multiplication. (d),(e) Two key circuit transformation widget. (d) A logical qubit begins from and ends at vector (1,1), respectively. (e) A diagonal 2-qubit gate on physical qubits is mapped into a single-qubit gate on a logical qubit.

Figure 2

Simulation of 1D and 2D random quantum circuits. (a)–(c) Quantum circuits are indicated by the volume of the yellow boxes. The lattice layouts of physical qubits are shown on the front surfaces of the boxes. The quantum information of the physical qubits flows along the direction of circuit depth and the quantum information of the defined logical qubits flows along the direction of circuit slices. (a) 1D quantum circuit with 1000 qubits and 42 depths. One logical qubit is defined for each circuit depth. (b) 2D quantum circuit with $125\times 8$ qubits and 42 depths. Eight logical qubits are defined for every eight circuit depths. (c) Modified 2D quantum circuit with $12\times 6$ qubits and 32 depths. Eleven logical qubits are defined for every eight circuit depths. (d) The layout of logical qubits for circuit (b). The world lines of physical qubits and entangling lines of 2-qubit gates inside the circuit slides are shown as gray lines. The entangling lines of 2-qubit gates across the circuit slices and all the single-qubit gates are not shown. The logical qubits flow inside the circuit slices (shown as red arrows) and across the circuit slices through the entangling gates between two neighboring slices (as shown as dashed lines).

Figure 3

Threshold rejection sampling protocol. (a) The ideal population distribution of a random quantum state is approximated by cut-peak distributions. Approximate distributions of 0.9, 0.7, and 0.5 fidelity are shown. (b) The trade-off between the sample fidelity and sampling efficiency. A sweet spot of 0.9 sample fidelity and 0.38 efficiency is obtained at a cut-peak threshold of $2.4\times 2^{-n}$.

Figure 4

New 49-qubit barrier. Our protocol extends the classically easy area of random quantum circuit sampling from area $A$ to area $B$, where the number of physical qubits or logical qubits (proportional to the circuit depth) is smaller than 49. The classically hard quantum sampling is in area $C$. Around the corner of area $C$, a small area $D$ may be classically easy by considering the trade-off between memory usage and running time. The star symbol represents the 1000 physical-qubit simulations in this Letter.