# MQI

## Seminar

### Exact quantum algorithms

Seminar Room 1, Newton Institute

#### Abstract

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.

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.