23 citations · 28 across the 8 of their papers we have counts for
4 papers · 1 filter
Separations in query complexity for total search problems
Shalev Ben-David, Srijita Kundu
We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we al…
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 algorithms for hypergraph simplex finding
Zhiying Yu, Shalev Ben-David
We study the quantum query algorithms for simplex finding, a generalization of triangle finding to hypergraphs. This problem satisfies a rank-reduction property: a quantum query al…
Oracle separation of QMA and QCMA with bounded adaptivity
Shalev Ben-David, Srijita Kundu
We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is smal…