Exact quantum algorithms
49 mins 50 secs,
190.61 MB,
iPod Video
480x270,
29.97 fps,
44100 Hz,
522.22 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) |