Search

Quantum error mitigation (QEM) can recover accurate expectation values from a noisy quantum computer by trading off bias for variance, such that an averaged result is more accurate but takes longer to converge. Probabilistic error cancellation (PEC) stands out among QEM methods as an especially robust means of controllably eliminating bias. However, PEC often exhibits a much larger variance than other methods, inhibiting application to large problems for a given error rate. Recent analyses have shown that the variance of PEC can be reduced by not mitigating errors lying outside the causal lightcone of the desired observable. Here, we improve the lightcone approach by classically computing tighter bounds on how much each error channel in the circuit can bias the final result. This set of bounds, which we refer to as a "shaded lightcone," enables a more targeted application of PEC, improving the tradespace of bias and variance, while illuminating how the structure of a circuit determines the difficulty of error-mitigated computation. Although a tight shaded lightcone is exponentially hard to compute, we present an algorithm providing a practical benefit for some problems even with modest classical resources, leveraging the ease of evolving an error instead of the state or the observable. The algorithm reduces the runtime that would be needed to apply PEC for a target accuracy in an example 127-qubit Trotter circuit by approximately two orders of magnitude compared to standard lightcone-PEC, expanding the domain of problems that can be computed via direct application of PEC on noisy hardware.

Quantum signal processing (QSP) provides a systematic framework for implementing a polynomial transformation of a linear operator, and unifies nearly all known quantum algorithms. In parallel, recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel and enables a quadratic suppression of error (i.e., $\epsilon \rightarrow O(\epsilon^2)$) at little to no overhead. Here we integrate randomized compiling into QSP through Stochastic Quantum Signal Processing. Our algorithm implements a probabilistic mixture of polynomials, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual polynomial. Because nearly all QSP-based algorithms exhibit query complexities scaling as $O(\log(1/\epsilon))$ -- stemming from a result in functional analysis -- this error suppression reduces their query complexity by a factor that asymptotically approaches $1/2$. By the unifying capabilities of QSP, this reduction extends broadly to quantum algorithms, which we demonstrate on algorithms for real and imaginary time evolution, phase estimation, ground state preparation, and matrix inversion.

In this paper, we introduce the gauge-fixed QLDPC surgery scheme, an improved logical measurement scheme based on the construction of Cohen et al.~(Sci.~Adv.~8, eabn1717). Our scheme leverages expansion properties of the Tanner graph to substantially reduce the space overhead of QLDPC surgery. In certain cases, we only require $\Theta(w)$ ancilla qubits to fault-tolerantly measure a weight $w$ logical operator. We provide rigorous analysis for the code distance and fault distance of our schemes, and present a modular decoding algorithm that achieves maximal fault-distance. We further introduce a bridge system to facilitate fault-tolerant joint measurements of logical operators. Augmented by this bridge construction, our scheme can be used to connect different families of QLDPC codes into one universal architecture. Applying our toolbox, we show how to perform all logical Clifford gates on the [[144,12,12]] bivariate bicycle code. Our scheme adds 103 ancilla qubits into the connectivity graph, and one of the twelve logical qubits is used as an ancilla for gate synthesis. Logical measurements are combined with the automorphism gates studied by Bravyi et al.~(Nature 627, 778-782) to implement 288 Pauli product measurements. We demonstrate the practicality of our scheme through circuit-level noise simulations, leveraging our proposed modular decoder that combines BPOSD with matching.

Computational models are an essential tool for the design, characterization, and discovery of novel materials. Hard computational tasks in materials science stretch the limits of existing high-performance supercomputing centers, consuming much of their simulation, analysis, and data resources. Quantum computing, on the other hand, is an emerging technology with the potential to accelerate many of the computational tasks needed for materials science. In order to do that, the quantum technology must interact with conventional high-performance computing in several ways: approximate results validation, identification of hard problems, and synergies in quantum-centric supercomputing. In this paper, we provide a perspective on how quantum-centric supercomputing can help address critical computational problems in materials science, the challenges to face in order to solve representative use cases, and new suggested directions., Comment: 65 pages, 15 figures; comments welcome

Quantum simulation traditionally relies on unitary dynamics, inherently imposing efficiency constraints on the generation of intricate entangled states. In principle, these limitations can be superseded by non-unitary, dynamic circuits. These circuits exploit measurements alongside conditional feed-forward operations, providing a promising approach for long-range entangling gates, higher effective connectivity of near-term hardware, and more efficient state preparations. Here, we explore the utility of shallow dynamic circuits for creating long-range entanglement on large-scale quantum devices. Specifically, we study two tasks: CNOT gate teleportation between up to 101 qubits by feeding forward 99 mid-circuit measurement outcomes, and the preparation of Greenberger-Horne-Zeilinger (GHZ) states with genuine entanglement. In the former, we observe that dynamic circuits can outperform their unitary counterparts. In the latter, by tallying instructions of compiled quantum circuits, we provide an error budget detailing the obstacles that must be addressed to unlock the full potential of dynamic circuits. Looking forward, we expect dynamic circuits to be useful for generating long-range entanglement in the near term on large-scale quantum devices., Comment: 7 pages, 3 figures (main text) + 11 pages, 6 figures (appendix)

Quantum error correction becomes a practical possibility only if the physical error rate is below a threshold value that depends on a particular quantum code, syndrome measurement circuit, and decoding algorithm. Here we present an end-to-end quantum error correction protocol that implements fault-tolerant memory based on a family of LDPC codes with a high encoding rate that achieves an error threshold of $0.8\%$ for the standard circuit-based noise model. This is on par with the surface code which has remained an uncontested leader in terms of its high error threshold for nearly 20 years. The full syndrome measurement cycle for a length-$n$ code in our family requires $n$ ancillary qubits and a depth-7 circuit composed of nearest-neighbor CNOT gates. The required qubit connectivity is a degree-6 graph that consists of two edge-disjoint planar subgraphs. As a concrete example, we show that 12 logical qubits can be preserved for nearly one million syndrome cycles using 288 physical qubits in total, assuming the physical error rate of $0.1\%$. We argue that achieving the same level of error suppression on 12 logical qubits with the surface code would require nearly 3000 physical qubits. Our findings bring demonstrations of a low-overhead fault-tolerant quantum memory within the reach of near-term quantum processors., Comment: numerical results are revised after fixing a bug in the simulation software

In superconducting architectures, limited connectivity remains a significant challenge for the synthesis and compilation of quantum circuits. We consider models of entanglement-assisted computation where long-range operations are achieved through injections of large GHZ states. These are prepared using ancillary qubits acting as an ``entanglement bus,'' unlocking global operation primitives such as multi-qubit Pauli rotations and fan out gates. We derive bounds on the circuit size for several well studied problems, such as CZ circuit, CX circuit, and Clifford circuit synthesis. In particular, in an architecture using one such entanglement bus, we give an $O(n^3)$-complexity synthesis scheme for arbitrary Clifford operations requiring at most $2n + 1$ layers of entangled-state-injections. In a square-lattice architecture with two entanglement buses, we show that a graph state can be synthesized using at most $\lceil \frac{1}{2}n \rceil + 1$ layers of GHZ state injections, and Clifford operations require only $\lceil\frac{3}{2} n \rceil + O(\sqrt n)$ layers of GHZ state injections., Comment: Update to include additional references on Clifford decomposition as transvections and Lempel's factorization for CZ synthesis, and corrected several typos

A promising avenue for the preparation of Gibbs states on a quantum computer is to simulate the physical thermalization process. The Davies generator describes the dynamics of an open quantum system that is in contact with a heat bath. Crucially, it does not require simulation of the heat bath itself, only the system we hope to thermalize. Using the state-of-the-art techniques for quantum simulation of the Lindblad equation, we devise a technique for the preparation of Gibbs states via thermalization as specified by the Davies generator. In doing so, we encounter a severe technical challenge: implementation of the Davies generator demands the ability to estimate the energy of the system unambiguously. That is, each energy of the system must be deterministically mapped to a unique estimate. Previous work showed that this is only possible if the system satisfies an unphysical 'rounding promise' assumption. We solve this problem by engineering a random ensemble of rounding promises that simultaneously solves three problems: First, each rounding promise admits preparation of a 'promised' thermal state via a Davies generator. Second, these Davies generators have a similar mixing time as the ideal Davies generator. Third, the average of these promised thermal states approximates the ideal thermal state., Comment: Accepted in Quantum

Amplitude estimation algorithms are based on Grover's algorithm: alternating reflections about the input state and the desired outcome. But what if we are given the ability to perform arbitrary rotations, instead of just reflections? In this situation, we find that quantum signal processing lets us estimate the amplitude in a more flexible way. We leverage this technique to give improved and simplified algorithms for many amplitude estimation tasks: we perform non-destructive estimation without any assumptions on the amplitude, develop an algorithm with improved performance in practice, present a new method for unbiased amplitude estimation, and finally give a simpler method for trading quantum circuit depth for more repetitions of short circuits., Comment: Accepted in Quantum

We introduce a fully constructive characterisation of holographic quantum error-correcting codes. That is, given a code and an erasure error we give a recipe to explicitly compute the terms in the RT formula. Using this formalism, we employ quantum circuits to construct a number of examples of holographic codes. Our codes have nontrivial holographic properties and are simpler than existing approaches built on tensor networks. Finally, leveraging a connection between correctable and private systems we prove the uniqueness of the algebra satisfying complementary recovery. The material is presented with the goal of accessibility to researchers in quantum information with no prior background in holography., Comment: v2: published version, typos fixed, 66 pages, 4 figures

We consider performing phase estimation under the following conditions: we are given only one copy of the input state, the input state does not have to be an eigenstate of the unitary, and the state must not be measured. Most quantum estimation algorithms make assumptions that make them unsuitable for this 'coherent' setting, leaving only the textbook approach. We present novel algorithms for phase, energy, and amplitude estimation that are both conceptually and computationally simpler than the textbook method, featuring both a smaller query complexity and ancilla footprint. They do not require a quantum Fourier transform, and they do not require a quantum sorting network to compute the median of several estimates. Instead, they use block-encoding techniques to compute the estimate one bit at a time, performing all amplification via singular value transformation. These improved subroutines accelerate the performance of quantum Metropolis sampling and quantum Bayesian inference., Comment: Added Jupyter notebook for reproducibility and fixed a benchmarking error

Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under "Goldilocks rules" that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms -- Rydberg arrays, trapped ions, and superconducting qubits -- can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA., Comment: 24 pages, 10 figures

We present quantum algorithms for the estimation of n-time correlation functions, the local and non-local density of states, and dynamical linear response functions. These algorithms are all based on block-encodings - a versatile technique for the manipulation of arbitrary non-unitary matrices on a quantum computer. We describe how to 'sketch' these quantities via the kernel polynomial method which is a standard strategy in numerical condensed matter physics. These algorithms use amplitude estimation to obtain a quadratic speedup in the accuracy over previous results, can capture any observables and Hamiltonians presented as linear combinations of Pauli matrices, and are modular enough to leverage future advances in Hamiltonian simulation and state preparation., Comment: 11 pages, 1 figure

In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a quantum algorithm for approximate counting. Given a list of $N$ items, $K$ of them marked, their algorithm estimates $K$ to within relative error $\varepsilon$ by making only $O\left( \frac{1}{\varepsilon}\sqrt{\frac{N}{K}}\right) $ queries. Although this speedup is of "Grover" type, the BHMT algorithm has the curious feature of relying on the Quantum Fourier Transform (QFT), more commonly associated with Shor's algorithm. Is this necessary? This paper presents a simplified algorithm, which we prove achieves the same query complexity using Grover iterations only. We also generalize this to a QFT-free algorithm for amplitude estimation. Related approaches to approximate counting were sketched previously by Grover, Abrams and Williams, Suzuki et al., and Wie (the latter two as we were writing this paper), but in all cases without rigorous analysis., Comment: Update November 2021: changed several constants throughout and gave an updated proof that simplifies the analysis. This also remedies an algebra mistake present in the previous version

We present novel algorithms to estimate outcomes for qubit quantum circuits. Notably, these methods can simulate a Clifford circuit in linear time without ever writing down stabilizer states explicitly. These algorithms outperform previous noisy near-Clifford techniques for most circuits. We identify a large class of input states that can be efficiently simulated despite not being stabilizer states. The algorithms leverage probability distributions constructed from Bloch vectors, paralleling previously known algorithms that use the discrete Wigner function for qutrits., Comment: 11 pages, 5 figures. This work is intended to supersede quant-ph/1804.05404

Verification of NISQ era quantum devices demands fast classical simulation of large noisy quantum circuits. We present an algorithm based on the stabilizer formalism that can efficiently simulate noisy stabilizer circuits. Additionally, the protocol can efficiently simulate a large set of multi-qubit mixed states that are not mixtures of stabilizer states. The existence of these 'bound states' was previously only known for odd-dimensional systems like qutrits. The algorithm also has the favorable property that circuits with depolarizing noise are simulated much faster than unitary circuits. This work builds upon a similar algorithm by Bennink et al. (Phys. Rev. A 95, 062337) and utilizes a framework by Pashayan et al. (Phys. Rev. Lett. 115, 070501)., Comment: 6 pages, 2 figures

Magic state distillation protocols have a complicated non-linear nature. Analysis of protocols is therefore usually restricted to one-parameter families of states, which aids tractability. We show that if we lift this one-parameter restriction and embrace the complexity, distillation exhibits fractal properties. By studying these fractals we demonstrate that some protocols are more effective when not restricted. Low fidelity states that are usually worthless for distillation are now usable, and fewer iterations of the protocols are needed to reach high fidelity., Comment: 10 pages

Many proposals for fault-tolerant quantum computation require injection of 'magic states' to achieve a universal set of operations. Some qubit states are above a threshold fidelity, allowing them to be converted into magic states via 'magic state distillation', a process based on stabilizer codes from quantum error correction. We define quantum weight enumerators that take into account the sign of the stabilizer operators. These enumerators completely describe the magic state distillation behavior when distilling T-type magic states. While it is straightforward to calculate them directly by counting exponentially many operator weights, it is also an NP-hard problem to compute them in general. This suggests that finding a family of distillation schemes with desired threshold properties is at least as hard as finding the weight distributions of a family of classical codes. Additionally, we develop search algorithms fast enough to analyze all useful 5 qubit codes and some 7 qubit codes, finding no codes that surpass the best known threshold., Comment: 10 pages, 1 figure