Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum pcp:
TR19-010 | 21st January 2019
Dorit Aharonov, Alex Bredariol Grilo

Stoquastic PCP vs. Randomness

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>

TR22-140 | 10th October 2022
Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry

Commitments to Quantum States

Revisions: 1

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the ... more >>>

TR23-178 | 16th November 2023
Louis Golowich, Tali Kaufman

NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

ISSN 1433-8092 | Imprint