Kyungjoo Noh

While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a quasi-polynomial-time classical algorithm for simulating quantum circuits under local depolarization noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markov property to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markov property in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate, including non-unital noises. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits and random circuits under non-unital noise, where anticoncentration does not hold and prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markov property and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage.

Abstract Quantum communication is an important branch of quantum information science, promising unconditional security to classical communication and providing the building block of a future large-scale quantum network. Noise in realistic quantum communication channels imposes fundamental limits on the communication rates of various quantum communication tasks. It is therefore crucial to identify or bound the quantum capacities of a quantum channel. Here, we consider Gaussian channels that model energy loss and thermal noise errors in realistic optical and microwave communication channels and study their various quantum capacities in the energy-constrained scenario. We provide improved lower bounds to various energy-constrained quantum capacities of these fundamental channels and show that higher communication rates can be attained than previously believed. Specifically, we show that one can boost the transmission rates of quantum information and private classical information by using a correlated multi-mode thermal state instead of the single-mode thermal state of the same energy.

We propose a novel architecture of quantum-error-correction-based quantum repeaters that combines the techniques used in discrete and continuous variable quantum information. Specifically, we propose to encode the transmitted qubits in a concatenated code consisting of two levels. On the first level we use a continuous variable GKP code which encodes the qubit in a single bosonic mode. On the second level we use a small discrete variable code, encoding a logical qubit in as few as seven physical qubits. Such an architecture introduces two major novelties which allow us to make efficient use of resources. Firstly, our architecture makes use of two types of quantum repeaters: the simpler GKP repeaters that need to only be able to store and correct errors on a single GKP qubit and more powerful but more costly multi-qubit repeaters that additionally can correct errors on the higher level. We find that the combination of using the two types of repeaters enables us to achieve performance needed in practical scenarios with a significantly reduced cost with respect to an architecture based solely on multiqubit repeaters. Secondly the use of continuous variable GKP code on the lower level has the advantage of providing us with the information about the success probability of the specific GKP correction round. This analog information, unique to bosonic codes, provides significant boost in performance when used to correct second level errors in the multi-qubit repeaters.