4 papers
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Itay Shalit, Mark Zhandry
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line…
Does Not Relativize
Adam Bouland, Andrew Huang, Anand Natarajan +2
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work d…
On the Cryptographic Structure Required for Verifying Qubits
James Bartusek, Itay Shalit
Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computatio…
Clifford Strategies in Interactive Protocols are Classically Simulatable
Itay Shalit
is the class of languages decidable by an efficient classical verifier interacting with multiple quantum provers that share entangled qubits but cannot communicat…