2-Forrelation is solvable with one or two IQP circuits, answering an open question on commuting quantum computations and strengthening the BQP vs PH oracle separation.
Fourier spectrum of noisy quantum algorithms
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative citing papers
A hybrid lifting theorem unifies classical query-to-communication and quantum approximate-degree lifting to prove c + q² = Ω(max{deg(f), bs(f)} log n) for protocols computing f ∘ G^n.
citing papers explorer
-
IQP circuits for 2-Forrelation
2-Forrelation is solvable with one or two IQP circuits, answering an open question on commuting quantum computations and strengthening the BQP vs PH oracle separation.
-
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
A hybrid lifting theorem unifies classical query-to-communication and quantum approximate-degree lifting to prove c + q² = Ω(max{deg(f), bs(f)} log n) for protocols computing f ∘ G^n.