Browsing Computer Science by Supervisor "Ben-David, Shalev"
Now showing items 1-3 of 3
-
A Generalized Adversary Method for Quantum Query Complexity
(University of Waterloo, 2022-05-20)Quantum query complexity measures the minimum number of queries a quantum algorithm needs to make to some input string to compute a function of that input. Query complexity models are widely used throughout quantum computing, ... -
On the power of interleaved low-depth quantum and classical circuits
(University of Waterloo, 2022-09-26)Low-depth quantum circuits are a well-suited model for near-term quantum devices, given short coherence times and noisy gate operations, making it pivotal to examine their computational power. It was already known as early ... -
Variants of Pseudo-deterministic Algorithms and Duality in TFNP
(University of Waterloo, 2023-08-18)We introduce a new notion of ``faux-deterministic'' algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over ...