Abstract | ||
---|---|---|
A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. In this paper, we present two new exact quantum algorithms for natural problems: 1) for the problem EXACT_k^n in which we have to determine whether the sequence of input bits x_1, ..., x_n contains exactly k values x_i=1; 2) for the problem THRESHOLD_k^n in which we have to determine if at least k of n input bits are equal to 1. |
Year | DOI | Venue |
---|---|---|
2013 | 10.4230/LIPIcs.TQC.2013.263 | conference on theory of quantum computation communication and cryptography |
Keywords | DocType | Volume |
quantum physics | Conference | abs/1302.1235 |
Citations | PageRank | References |
10 | 0.64 | 10 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andris Ambainis | 1 | 2000 | 183.24 |
Janis Iraids | 2 | 18 | 6.14 |
Juris Smotrovs | 3 | 51 | 7.35 |