We formulate a mixed-state analog of the NLTS conjecture [FH14] by asking whether there exist topologically-ordered systems for which the thermal Gibbs state for constant temperature is globally-entangled in the sense that it cannot even be approximated by shallow quantum circuits. We then prove this conjecture holds for nearly optimal parameters: when the "inverse temperature" is almost a constant (temperature decays as 1/loglog(n))) and the Hamiltonian is nearly local (log(n)-local). The construction and proof combine quantum codes that arise from high-dimensional manifolds [Has17, LLZ19], the local-decoding approach to quantum codes [LTZ15, FGL18] and quantum locally-testable codes [AE15].

The existence of quantum LDPC codes with minimal distance scaling linearly in the number of qubits is a central open problem in quantum information. Despite years of research good quantum LDPC codes are not known to exist, but at the very least it is known they cannot be defined on very regular topologies, like low-dimensional grids. In this work we establish a complementary result, showing that good quantum CSS codes which are sparsely generated require “structure” in the local terms that constrain the code space so as not to be “too-random” in a well-defined sense. To show this, we prove a weak converse to a theorem of Krasikov and Litsyn on weight distributions of classical codes due to which may be of independent interest: subspaces for which the distribution of weights in the dual space is approximately binomial have very few codewords of low weight, tantamount to having a non-negligible “approximate” minimal distance. While they may not have a large minimal non-zero weight, they still have very few words of low Hamming weight.

The permanent is #P-hard to compute exactly on average for natural random matrices including matrices over finite fields or Gaussian ensembles. Should we expect that it remains #P-hard to compute on average if we only care about approximation instead of exact computation? In this work we take a first step towards resolving this question: We present a quasi-polynomial time deterministic algorithm for approximating the permanent of a typical n × n random matrix with unit variance and vanishing mean μ = O(ln ln n)-1/8to within inverse polynomial multiplicative error. (alternatively, one can achieve permanent approximation for matrices with mean μ = 1/polylog(n) in time 2n(ε), for arbitrarily small ε>0). The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix [1], [2] it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1) Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean μ. 2) Biased Bernoulli: each entry is -1 + μ with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness [3] of computing the permanent of a zero mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that becomes easy only when average case analysis and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok [1], [4], [5], [6] who used Taylor series approximation of the logarithm of a certain univariate polynomial related to the permanent. Our main contribution is to introduce an average-case analysis of such related polynomials. We complement our approach with a new technique for iteratively computing a Taylor series approximation of a function that is analytical in the vicinity of a curve in the complex plane. This method can be viewed as a computational version of analytic continuation in complex analysis.

Inspired by quantum computing algorithms for Linear Algebra problems [Harrow et al., Phys. Rev. Lett. 2009, Ta-Shma, STOC 2013] we study how simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log^2(n)) parallel time with a total cost of O(n^(\omega+1)) Boolean operations. This Boolean complexity matches the best known O(log^2(n)) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so it may lead to actual implementations, allowing fast parallel computation of eigenvectors and eigenvalues in practice. Previous approaches to solve the Eigen-Problem generally use randomization to avoid bad conditions - as we do. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod 2pi) is the main technical contribution of this work. It relies on the theory of low-discrepancy or quasi-random sequences - a theory, which to the best of our knowledge, has not been connected thus far to linear algebra problems. Hence, we believe that further study of this new connection will lead to additional improvements.

Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them, even approximately, must be sufficiently deep to allow coupling (entanglement) between any pair of qubits. Until now this property was not known to be “robust” - the marginals of such states to a subset of the qubits containing all but a small constant fraction of them may be only locally entangled, and hence approximable by shallow quantum circuits. In this work we construct a family of 16-local Hamiltonians for which any marginal of a ground state to a fraction at least 1-10-8of the qubits must be globally entangled. This provides evidence that quantum entanglement is not very fragile, and perhaps our intuition about its instability is an artifact of considering local Hamiltonians which are not only local but spatially local. Formally, it provides positive evidence for two wide-open conjectures in condensed-matter physics and quantum complexity theory which are the qLDPC conjecture, positing the existence of “good” quantum LDPC codes, and the NLTS conjecture [1] positing the existence of local Hamiltonians in which any low-energy state is highly entangled. Our Hamiltonian is based on applying the hypergraph product by Tillich-Zemor [2] to the repetition code with checks from an expander graph. A key tool in our proof is a new lower bound on the vertex expansion of the output of low-depth quantum circuits, which may be of independent interest.

We initiate the study of quantum locally testable codes ($\text{qLTC}$s). Classical $\text{LTC}$s are very important in computational complexity. These codes are defined as the linear subspace satisfying a set of local constraints, with the additional requirement that their soundness, $R(\delta)$, which is the probability that a randomly chosen constraint is violated, is proportional to the proximity $\delta$, where $\delta n$ is the distance of a word from the code. Excellent $\text{LTC}$s exist in the classical world, and they are tightly related to the celebrated $\text{PCP}$ (probabilistically checkable proof) theorem. In quantum complexity, quantum error correcting codes provide central examples in the study of the illusive behavior of multiparticle entanglement, and they have played a crucial role in many computational complexity results. We provide a definition of the quantum analogue of $\text{LTC}$s and motivate it by connecting its central notions in the study of both entanglement and quantum Hamiltonian complexity. A natural question is whether such codes exist, and how good can their soundness be. To the best of our knowledge all quantum codes known today exhibit poor soundness. Moreover, we show that the soundness of $\text{CSS}$ codes (which are commonly used quantum codes defined by two classical codes) is governed by the minimal soundness of the two classical codes; in the most natural $\text{CSS}$ code we examined as a candidate $\text{qLTC}$, namely, the Reed--Muller code, there is a tradeoff between the parameters of the two codes, which prevents the resulting quantum code from being $\text{qLTC}$. These facts seem to suggest a more general phenomenon, by which the soundness of $\text{qLTC}$s is inherently restricted due to multiparticle entanglement. Our main technical contribution consists of two complementary results regarding $\text{qLTC}$s which are stabilizer codes (denoted $\text{sLTC}$s). We first prove a surprising, inherently quantum property of $\text{sLTC}$s. For small constant values of proximity, the better the local expansion of the interaction graph of the constraints, the less sound the $\text{sLTC}$ becomes. This stands in sharp contrast to the classical setting. The complementary, more intuitive result also holds (and is actually much more involved technically to prove in the quantum case): an upper bound on the soundness when the code is defined on bad local expanders. Together we arrive at a quantum upper bound on the soundness of $\text{sLTC}$s set on any graph, which does not hold in the classical case. Many open questions are raised regarding what possible parameters are achievable for $\text{qLTC}$s, and their relation to other objects of interest in quantum information theory. In the appendix we also define a quantum analogue of $\text{PCP}$s of proximity ($\text{PCPP}$s) and point out that the result of [E. Ben-Sasson et al., SIAM J. Comput., 36 (2006), pp. 889--974] by which $\text{PCPP}$s imply $\text{LTC}$s with related parameters carries over to the $\text{sLTC}$s. This creates a first link between $\text{qLTC}$s and quantum $\text{PCP}$s [D. Aharonov, I. Arad, and T. Vidick, ACM SIGACT News Archive, 44 (2013), pp. 47--79].

The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.