Approximate QLDPC codes from spacetime Hamiltonians

Friday, April 12, 2019 10:15 am - 10:15 am EDT (GMT -04:00)

Chinmay Nirkhe, University of California, Berkeley

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 stabilizergenerator 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,ε]] approximate QLDPC codes that encode k = Ω(N/polylog N) into N physical qubits with distance d = Ω(N / polylog N) and approximation infidelity ε = 1/polylog N.

Relevant papers:  

https://arxiv.org/abs/1811.00277 (joint work with Thom Bohdanowicz, Elizabeth Crosson, and Henry Yuen)
https://arxiv.org/abs/1802.07419 (joint with Henry Yuen and Umesh Vazirani)

About the speaker

Chinmay Nirkhe is a PhD student at UC Berkeley. His research interests are in theoretical computer science, centered around quantum information and hardness of approximation. Some of his favorite research topics are the qPCP conjecture, multiprover interactive proofs, and quantum supremacy.