Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that yes instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantu
m setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.
Stabilized cat codes can provide a biased noise channel with a set of bias-preserving (BP) gates, which can significantly reduce the resource overhead for fault-tolerant quantum computing. All existing schemes of BP gates, however, require adiabatic
quantum evolution, with performance limited by excitation loss and non-adiabatic errors during the adiabatic gates. In this work, we apply a derivative-based leakage suppression technique to overcome non-adiabatic errors, so that we can implement fast BP gates on Kerr-cat qubits with improved gate fidelity while maintaining high noise bias. When applied to concatenated quantum error correction, the fast BP gates can not only improve the logical error rate but also reduce resource overhead, which enables more efficient implementation of fault-tolerant quantum computing.
The Quantum Approximate Optimization Algorithm, QAOA, uses a shallow depth quantum circuit to produce a parameter dependent state. For a given combinatorial optimization problem instance, the quantum expectation of the associated cost function is the
parameter dependent objective function of the QAOA. We demonstrate that if the parameters are fixed and the instance comes from a reasonable distribution then the objective function value is concentrated in the sense that typical instances have (nearly) the same value of the objective function. This applies not just for optimal parameters as the whole landscape is instance independent. We can prove this is true for low depth quantum circuits for instances of MaxCut on large 3-regular graphs. Our results generalize beyond this example. We support the arguments with numerical examples that show remarkable concentration. For higher depth circuits the numerics also show concentration and we argue for this using the Law of Large Numbers. We also observe by simulation that if we find parameters which result in good performance at say 10 bits these same parameters result in good performance at say 24 bits. These findings suggest ways to run the QAOA that reduce or eliminate the use of the outer loop optimization and may allow us to find good solutions with fewer calls to the quantum computer.
We consider two-dimensional states of matter satisfying an uniform area law for entanglement. We show that the topological entanglement entropy is equal to the minimum relative entropy distance from the reduced state to the set of thermal states of l
ocal models. The argument is based on strong subadditivity of quantum entropy. For states with zero topological entanglement entropy, in particular, the formula gives locality of the states at the boundary of a region as thermal states of local Hamiltonians. It also implies that the entanglement spectrum of a two-dimensional region is equal to the spectrum of a one-dimensional local thermal state on the boundary of the region.
Quantum error correction was invented to allow for fault-tolerant quantum computation. Systems with topological order turned out to give a natural physical realization of quantum error correcting codes (QECC) in their groundspaces. More recently, in
the context of the AdS/CFT correspondence, it has been argued that eigenstates of CFTs with a holographic dual should also form QECCs. These two examples raise the question of how generally eigenstates of many-body models form quantum codes. In this work we establish new connections between quantum chaos and translation-invariance in many-body spin systems, on one hand, and approximate quantum error correcting codes (AQECC), on the other hand. We first observe that quantum chaotic systems exhibiting the Eigenstate Thermalization Hypothesis (ETH) have eigenstates forming approximate quantum error-correcting codes. Then we show that AQECC can be obtained probabilistically from translation-invariant energy eigenstates of every translation-invariant spin chain, including integrable models. Applying this result to 1D classical systems, we describe a method for using local symmetries to construct parent Hamiltonians that embed these codes into the low-energy subspace of gapless 1D quantum spin chains. As explicit examples we obtain local AQECC in the ground space of the 1D ferromagnetic Heisenberg model and the Motzkin spin chain model with periodic boundary conditions, thereby yielding non-stabilizer codes in the ground space and low energy subspace of physically plausible 1D gapless models.
Chaotic dynamics in quantum many-body systems scrambles local information so that at late times it can no longer be accessed locally. This is reflected quantitatively in the out-of-time-ordered correlator of local operators, which is expected to deca
y to zero with time. However, for systems of finite size, out-of-time-ordered correlators do not decay exactly to zero and in this paper we show that the residual value can provide useful insights into the chaotic dynamics. When energy is conserved, the late-time saturation value of the out-of-time-ordered correlator of generic traceless local operators scales as an inverse polynomial in the system size. This is in contrast to the inverse exponential scaling expected for chaotic dynamics without energy conservation. We provide both analytical arguments and numerical simulations to support this conclusion.
Thermal states are the bedrock of statistical physics. Nevertheless, when and how they actually arise in closed quantum systems is not fully understood. We consider this question for systems with local Hamiltonians on finite quantum lattices. In a fi
rst step, we show that states with exponentially decaying correlations equilibrate after a quantum quench. Then we show that the equilibrium state is locally equivalent to a thermal state, provided that the free energy of the equilibrium state is sufficiently small and the thermal state has exponentially decaying correlations. As an application, we look at a related important question: When are thermal states stable against noise? In other words, if we locally disturb a closed quantum system in a thermal state, will it return to thermal equilibrium? We rigorously show that this occurs when the correlations in the thermal state are exponentially decaying. All our results come with finite-size bounds, which are crucial for the growing field of quantum thermodynamics and other physical applications.
Preparing quantum thermal states on a quantum computer is in general a difficult task. We provide a procedure to prepare a thermal state on a quantum computer with a logarithmic depth circuit of local quantum channels assuming that the thermal state
correlations satisfy the following two properties: (i) the correlations between two regions are exponentially decaying in the distance between the regions, and (ii) the thermal state is an approximate Markov state for shielded regions. We require both properties to hold for the thermal state of the Hamiltonian on any induced subgraph of the original lattice. Assumption (ii) is satisfied for all commuting Gibbs states, while assumption (i) is satisfied for every model above a critical temperature. Both assumptions are satisfied in one spatial dimension. Moreover, both assumptions are expected to hold above the thermal phase transition for models without any topological order at finite temperature. As a building block, we show that exponential decay of correlation (for thermal states of Hamiltonians on all induced subgraph) is sufficient to efficiently estimate the expectation value of a local observable. Our proof uses quantum belief propagation, a recent strengthening of strong sub-additivity, and naturally breaks down for states with topological order.
We prove that any one-dimensional (1D) quantum state with small quantum conditional mutual information in all certain tripartite splits of the system, which we call a quantum approximate Markov chain, can be well-approximated by a Gibbs state of a sh
ort-range quantum Hamiltonian. Conversely, we also derive an upper bound on the (quantum) conditional mutual information of Gibbs states of 1D short-range quantum Hamiltonians. We show that the conditional mutual information between two regions A and C conditioned on the middle region B decays exponentially with the square root of the length of B. These two results constitute a variant of the Hammersley-Clifford theorem (which characterizes Markov networks, i.e. probability distributions which have vanishing conditional mutual information, as Gibbs states of classical short-range Hamiltonians) for 1D quantum systems. The result can be seen as a strengthening - for 1D systems - of the mutual information area law for thermal states. It directly implies an efficient preparation of any 1D Gibbs state at finite temperature by a constant-depth quantum circuit.
We consider entanglement distillation under the assumption that the input states are allowed to be correlated among each other. We hence replace the usually considered independent and identically-distributed hypothesis by the weaker assumption of mer
ely having identical reductions. We find that whether a state is then distillable or not is only a property of these reductions, and not of the correlations that are present in the input state. This is shown by establishing an appealing relation between the set of copy-correlated undistillable states and the standard set of undistillable states: The former turns out to be the convex hull of the latter. As an example of the usefulness of our approach to the study of entanglement distillation, we prove a new activation result, which generalizes earlier findings: it is shown that for every entangled state and every positive integer k, there exists a copy-correlated k-undistillable state such that their tensor product is single-copy distillable. Finally, the relation of our results to the conjecture about the existence of bound entangled states with a non-positive partial transpose is discussed.
