13 citations · 13 across the 3 of their papers we have counts for
5 papers
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…
Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
Gabor Ivanyos, Frederic Magniez, Miklos Santha
In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden…
Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates
Wim van Dam, Frederic Magniez, Michele Mosca +1
We consider the design of self-testers for quantum gates. A self-tester for the gates F_1,...,F_m is a classical procedure that, given any gates G_1,...,G_m, decides with high prob…