Learning Logical Pauli Noise in Quantum Error Correction.

The characterization of quantum devices is crucial for their practical implementation but can be costly in experimental effort and classical postprocessing. Therefore, it is desirable to measure only the information that is relevant for specific applications and develop protocols that require little additional effort. In this Letter, we focus on the characterization of quantum computers in the context of stabilizer quantum error correction. For arbitrary stabilizer codes, subsystem codes, and data syndrome codes, we prove that the logical error channel induced by Pauli noise can be estimated from syndrome data under minimal conditions. More precisely, for any such code, we show that the estimation is possible as long as the code can correct the noise.

Training Variational Quantum Algorithms Is NP-Hard.

Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.

Sample Complexity of Device-Independently Certified "Quantum Supremacy".

Results on the hardness of approximate sampling are seen as important stepping stones toward a convincing demonstration of the superior computational power of quantum devices. The most prominent suggestions for such experiments include boson sampling, instantaneous quantum polynomial time (IQP) circuit sampling, and universal random circuit sampling. A key challenge for any such demonstration is to certify the correct implementation. For all these examples, and in fact for all sufficiently flat distributions, we show that any noninteractive certification from classical samples and a description of the target distribution requires exponentially many uses of the device. Our proofs rely on the same property that is a central ingredient for the approximate hardness results, namely, that the sampling distributions, as random variables depending on the random unitaries defining the problem instances, have small second moments.

Reliable quantum certification of photonic state preparations.

Quantum technologies promise a variety of exciting applications. Even though impressive progress has been achieved recently, a major bottleneck currently is the lack of practical certification techniques. The challenge consists of ensuring that classically intractable quantum devices perform as expected. Here we present an experimentally friendly and reliable certification tool for photonic quantum technologies: an efficient certification test for experimental preparations of multimode pure Gaussian states, pure non-Gaussian states generated by linear-optical circuits with Fock-basis states of constant boson number as inputs, and pure states generated from the latter class by post-selecting with Fock-basis measurements on ancillary modes. Only classical computing capabilities and homodyne or hetorodyne detection are required. Minimal assumptions are made on the noise or experimental capabilities of the preparation. The method constitutes a step forward in many-body quantum certification, which is ultimately about testing quantum mechanics at large scales.

Quasilocality and efficient simulation of markovian quantum dynamics.

We consider open many-body systems governed by a time-dependent quantum master equation with short-range interactions. With a generalized Lieb-Robinson bound, we show that the evolution in this very generic framework is quasilocal; i.e., the evolution of observables can be approximated by implementing the dynamics only in a vicinity of the observables' support. The precision increases exponentially with the diameter of the considered subsystem. Hence, time evolution can be simulated on classical computers with a cost that is independent of the system size. Providing error bounds for Trotter decompositions, we conclude that the simulation on a quantum computer is additionally efficient in time. For experiments and simulations in the Schrödinger picture, our result can be used to rigorously bound finite-size effects.

Real-space renormalization yields finite correlations.

Real-space renormalization approaches for quantum lattice systems generate certain hierarchical classes of states that are subsumed by the multiscale entanglement renormalization Ansatz (MERA). It is shown that, with the exception of one spatial dimension, MERA states are actually states with finite correlations, i.e., projected entangled pair states (PEPS) with a bond dimension independent of the system size. Hence, real-space renormalization generates states which can be encoded with local effective degrees of freedom, and MERA states form an efficiently contractible class of PEPS that obey the area law for the entanglement entropy. It is further pointed out that there exist other efficiently contractible schemes violating the area law.