6 papers
The Information Complexity of Decision Trees
Avantika Agarwal, Shalev Ben-David, Eric Blais
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size…
Enhanced quantum capacity thresholds from symmetry
Avantika Agarwal, Amolak Ratan Kalra, Sungjai Lee +4
The quantum capacity captures the value of a quantum channel for transmitting quantum information, establishing the fundamental limits on quantum communication. In spite of its cen…
On Error Thresholds for Pauli Channels: Some answers with many more questions
Avantika Agarwal, Alan Bu, Amolak Ratan Kalra +3
This paper focuses on error thresholds for Pauli channels. We numerically compute lower bounds for the thresholds using the analytic framework of coset weight enumerators pioneered…
Non-Standard Oracles for Bounded-Error Complexity Classes
Avantika Agarwal, Srijita Kundu
In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptograp…
Oracle Separations for the Quantum-Classical Polynomial Hierarchy
Avantika Agarwal, Shalev Ben-David
We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum…
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1
The Polynomial-Time Hierarchy () is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…