COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Exact quantum algorithms

## Exact quantum algorithmsAdd 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. |
## Other listsInstitute Seminar DAMTP atmosphere-ocean Spring School 2008 - Translating animal models to patients with Neurodegenerative disorders## Other talksDiagnostics and patient pathways in pancreatic cancer Future directions panel Simulating Neutron Star Mergers From ‘Do Not Touch’ signs to barriers: can we successfully provide access without compromising preservation principles? Cambridge-Lausanne Workshop 2018 - Day 1 Aspects of adaptive Galerkin FE for stochastic direct and inverse problems |