104 citations
- Centrum Wiskunde & InformaticaNL3 papers
- University of CopenhagenDK3 papers
- University of HertfordshireGB3 papers
- European Southern ObservatoryCL2 papers
- Marshall Space Flight CenterUS2 papers
- Space Telescope Science InstituteUS2 papers
- University of LeicesterGB2 papers
- Albert Einstein College of MedicineUS1 paper
- California Institute of TechnologyUS1 paper
- City University of New YorkUS1 paper
- College of Western IdahoUS1 paper
- Consejo Superior de Investigaciones CientíficasES1 paper
6 papers · 1 filter
Quantum Algorithms for Matching and Network Flows
Andris Ambainis, Robert Spalek
We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{m+n} log n), finding a maximal non-bipartite matching in time…
Implications of Superstrong Nonlocality for Cryptography
Harry Buhrman, Matthias Christandl, Falk Unger +2
Non-local boxes are hypothetical ``machines'' that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/CHSH inequalities than is possible withi…
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…
An atom interferometer enabled by spontaneous decay
R. A. Cornelussen, R. J. C. Spreeuw, H. B. van Linden van den Heuvell
We investigate the question whether Michelson type interferometry is possible if the role of the beam splitter is played by a spontaneous process. This question arises from an insp…
Fault-Tolerant Quantum Computation For Local Non-Markovian Noise
Barbara M. Terhal, Guido Burkard
We derive a threshold result for fault-tolerant quantum computation for local non-Markovian noise models. The role of error amplitude in our analysis is played by the product of th…
Charge detection enables free-electron quantum computation
C. W. J. Beenakker, D. P. DiVincenzo, C. Emary +1
It is known that a quantum computer operating on electron-spin qubits with single-electron Hamiltonians and assisted by single-spin measurements can be simulated efficiently on a c…