Exact quantum algorithms

Add to your list(s) Download to your calendar using vCal

• Ambainis, A (University of Latvia)
• Friday 06 September 2013, 15:30-16:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Mathematical Challenges in Quantum Information

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1) – in contrast to the usual model in which a quantum algorithm is allowed to output an incorrect answer with a small probabilities. Coming up with exact quantum algorithms is a difficult task because we have to ensure that no amplitude ends up in a state corresponding to an incorrect answer – on any input.

We present the first example of a Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675…}) queries.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.