Content deleted Content added
m Dated {{Clarify}}. (Build p613) |
|||
Line 70:
| title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
| journal = [[SIAM Journal of Scientific and Statistical Computing]]
| volume = 26 | page = 1484
| arxiv = quant-ph/9508027
| bibcode= 1995quant.ph..8027S
Line 121:
=== Fourier fishing and Fourier checking ===
We have an [[oracle]] consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z<sub>1</sub>,..., z<sub>n</sub> such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy
:<math>\left| \tilde{f}\left( z_i \right) \right| \geqslant 1</math>
and at least 1/4 satisfies
Line 213:
The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, Ω(''N'') queries are required for a list of size ''N'', since this problem is harder than the search problem which requires Ω(''N'') queries. However, it can be solved in <math>\Theta(N^{2/3})</math> queries on a quantum computer. The optimal algorithm is by [[Andris Ambainis]].<ref>
{{cite journal
|last=Ambainis |first=A.
|year=2007
|title=Quantum Walk Algorithm for Element Distinctness
|journal=[[SIAM Journal on Computing]]
|volume=37 |issue=1 |pages=210–239
Line 226:
| last1=Aaronson | first1=S.
| last2=Shi | first2=Y.
| year=2004
| title=Quantum lower bounds for the collision and the element distinctness problems
| journal=[[Journal of the ACM]]
Line 244:
|doi=10.4086/toc.2005.v001a003
}}</ref> and Kutin<ref>
{{cite journal
|last1=Kutin |first1=S.
|year=2005
|title=Quantum Lower Bound for the Collision Problem with Small Range
|journal=[[Theory of Computing]]
|volume=1 |issue=1 |pages=29–36
Line 266:
|year=2007
|title=Search via quantum walk
|booktitle=Proceedings of the 39th Annual ACM Symposium on Theory of Computing
|publisher=[[Association for Computing Machinery]]
|pages=575–584
Line 279:
|title=Quantum Algorithms for the Triangle Problem
|journal=[[SIAM Journal of Computing]]
|volume=37 |issue=2 |pages=413–424
|arxiv=
|bibcode=
Line 309:
|isbn=0-8186-0740-8
}}</ref> (where <math>c = \log_2[(1+\sqrt{33})/4] \approx 0.754</math>), but can be solved in Θ(''N''<sup>0.5</sup>) queries by a quantum algorithm. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.<ref name=Hamiltonian_NAND_Tree/> The same result for the standard setting soon followed.<ref>
{{cite arxiv
|last=Ambainis |first=A.
|year=2007
Line 375:
| title=Simulating physics with computers
| journal=[[International Journal of Theoretical Physics]]
| volume=21 | issue=6–7 | page=467
| arxiv=
| bibcode = 1982IJTP...21..467F
Line 391:
| doi=10.1103/PhysRevLett.79.2586
}}</ref> and in particular, the simulation of chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits.<ref>
{{Cite journal
| last1=Kassal | first1=I.
| last2=Jordan | first2=S. P.
Line 403:
| arxiv= 0801.2986
| bibcode = 2008PNAS..10518681K
| doi=10.1073/pnas.0808245105
| pmc=2596249
| pmid=19033207
}}</ref> Quantum computers can also efficiently simulate topological quantum field theories.<ref>
{{Cite journal
Line 418:
| bibcode = 2002CMaPh.227..587F
| doi=10.1007/s002200200635
}}</ref> In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating "quantum"{{
{{Cite journal
| last1=Aharonov | first1=D.
| last2=Jones | first2=V.
| last3=Landau | first3=Z.
| year=2009
| title=A polynomial quantum algorithm for approximating the Jones polynomial
| journal=[[Algorithmica]]
Line 464:
{{quantum computing}}
{{Use dmy dates|date=September 2011}}
{{DEFAULTSORT:Quantum Algorithm}}
| |||