chinmay nirkhe

We study approximate quantum low-density parity-check (QLDPC) codes, which are approximate quantum error-correcting codes specified as the ground space of a frustration-free local Hamiltonian, whose terms do not necessarily commute. Such codes generalize stabilizer QLDPC codes, which are exact quantum error-correcting codes with sparse, low-weight stabilizer generators (i.e. each stabilizer generator acts on a few qubits, and each qubit participates in a few stabilizer generators). Our investigation is motivated by an important question in Hamiltonian complexity and quantum coding theory: do stabilizer QLDPC codes with constant rate, linear distance, and constant-weight stabilizers exist?

We show that obtaining such optimal scaling of parameters (modulo polylogarithmic corrections) is possible if we go beyond stabilizer codes: we prove the existence of a family of $[[N,k,d,\epsilon]]$ approximate QLDPC codes that encode $k=\widetilde{\Omega}(N)$ logical qubits into $N$ physical qubits with distance $d=\widetilde{\Omega}(N)$ and approximation infidelity $\epsilon=\mathcal{O}(1/\textrm{polylog}(N))$. The code space is stabilized by a set of 10-local noncommuting projectors, with each physical qubit only participating in $\textrm{polylog}(N)$ projectors. We prove the existence of an efficient encoding map, and we show that arbitrary Pauli errors can be locally detected by circuits of polylogarithmic depth. Finally, we show that the spectral gap of the code Hamiltonian is $\widetilde{\Omega}(N^{-3.09})$ by analyzing a spacetime circuit-to-Hamiltonian construction for a bitonic sorting network architecture that is spatially local in $\textrm{polylog}(N)$ dimensions.

A previous version of this paper appeared under the title: 'Quantum Supremacy and the Complexity of Random Circuit Sampling'.

A critical milestone on the path to useful quantum computers is the demonstration of a quantum computation that is prohibitively hard for classical computers—a task referred to as quantum supremacy. A leading near-term candidate is sampling from the probability distributions of randomly chosen quantum circuits, which we call random circuit sampling (RCS). RCS was defined with experimental realizations in mind, leaving its computational hardness unproven. Here we give strong complexity-theoretic evidence of classical hardness of RCS, placing it on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition, which is critical to establishing computational hardness in the presence of experimental noise. In addition, it follows from known results that RCS also satisfies an anti-concentration property, namely that errors in estimating output probabilities are small with respect to the probabilities themselves. This makes RCS the first proposal for quantum supremacy with both of these properties. Finally, we also give a natural condition under which an existing statistical measure, cross-entropy, verifies RCS, as well as describe a new verification measure that in some formal sense maximizes the information gained from experimental samples.

The No Low-Energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation 2014), which asserts the existence of local Hamiltonians whose low energy states cannot be generated by constant depth quantum circuits, identifies a fundamental obstacle to resolving the quantum PCP conjecture. Progress towards the NLTS conjecture was made by Eldar and Harrow (Foundations of Computer Science 2017), who proved a closely related theorem called No Low-Error Trivial States (NLETS). In this paper, we give a much simpler proof of the NLETS theorem, and use the same technique to establish superpolynomial circuit size lower bounds for noisy ground states of local Hamiltonians (assuming QCMA not equal to QMA), resolving an open question of Eldar and Harrow. We discuss the new light our results cast on the relationship between NLTS and NLETS.

Finally, our techniques imply the existence of approximate quantum low-weight check (qLWC) codes with linear rate, linear distance, and constant weight checks. These codes are similar to quantum LDPC codes except (1) each particle may participate in a large number of checks, and (2) errors only need to be corrected up to fidelity 1 - 1/poly(n). This stands in contrast to the best-known stabilizer LDPC codes due to Freedman, Meyer, and Luo which achieve a distance of O(sqrt{n log n}).

The principal technique used in our results is to leverage the Feynman-Kitaev clock construction to approximately embed a subspace of states defined by a circuit as the ground space of a local Hamiltonian.

chinmay nirkhe

Contact Information

Education

Papers

Talks

Teaching Assistant Positions

CV

Personal