A new construction of flat degree-d Hamiltonians with exp(Theta(d^2)) nonzero Pauli terms makes the noncommutative Bohnenblust-Hille constant exponential and refutes the quantum Fourier Entropy-Influence conjecture.
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly is contained in PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly is contained in PP/poly and that QMA/rpoly = QMA/poly.
fields
math.FA 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Dense Hamiltonians at the Parseval Limit: The Noncommutative BH Constant is Exponential and the Quantum FEI Conjecture is False
A new construction of flat degree-d Hamiltonians with exp(Theta(d^2)) nonzero Pauli terms makes the noncommutative Bohnenblust-Hille constant exponential and refutes the quantum Fourier Entropy-Influence conjecture.