23 citations · 36 across the 4 of their papers we have counts for
4 papers
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
We introduce two new complexity measures for Boolean functions, or more generally for functions of the form f:S->T. We call these measures sumPI and maxPI. The quantity sumPI has b…
Spectra of Quantized Walks and a rule
Mario Szegedy
We introduce quantized bipartite walks, compute their spectra, generalize the algorithms of Grover \cite{g} and Ambainis \cite{amb03} and interpret them as quantum walks with memor…
On the Quantum Query Complexity of Detecting Triangles in Graphs
Mario Szegedy
We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on nodes can be done using quantum queries.…
Quantum Algorithms for the Triangle Problem
Frederic Magniez, Miklos Santha, Mario Szegedy
We present two new quantum algorithms that either find a triangle (a copy of ) in an undirected graph on nodes, or reject if is triangle free. The first algorith…