Exact quantum algorithms
49 mins 53 secs,
91.26 MB,
MP3
44100 Hz,
249.77 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Ambainis, A (University of Latvia)
Friday 06 September 2013, 15:30-16:30 |
|---|
| Created: | 2013-09-09 16:20 |
|---|---|
| Collection: | Mathematical Challenges in Quantum Information |
| Publisher: | Isaac Newton Institute |
| Copyright: | Ambainis, A |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| 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. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.92 Mbits/sec | 719.77 MB | View | Download | |
| WebM | 640x360 | 851.03 kbits/sec | 310.72 MB | View | Download | |
| iPod Video | 480x270 | 522.22 kbits/sec | 190.61 MB | View | Download | |
| MP3 * | 44100 Hz | 249.77 kbits/sec | 91.26 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||