13 citations · 21 across the 7 of their papers we have counts for
8 papers · 1 filter
A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
Andrew M. Childs, Stacey Jeffery, Robin Kothari +1
We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness wit…
Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
Troy Lee, Frederic Magniez, Miklos Santha
We show that the quantum query complexity of detecting if an -vertex graph contains a triangle is . This improves the previous best algorithm of Belovs making $O(n^{…
Self-Testing of Quantum Circuits
Frederic Magniez, Dominic Mayers, Michele Mosca +1
We prove that a quantum circuit together with measurement apparatuses and EPR sources can be fully verified without any reference to some other trusted set of quantum devices. Our…
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Sophie Laplante, Frederic Magniez
We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmo…
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…
Quantum testers for hidden group properties
Katalin Friedl, Frederic Magniez, Miklos Santha +1
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in t…