Content deleted Content added
→BQP-complete problems: ce refs |
Citation bot (talk | contribs) |
||
Line 86:
|editor-last=Coppersmith |editor-first=D.
|title=CRYPTO '95, [[Lecture Notes in Computer Science]]
|pages=
|publisher=[[Springer-Verlag]]
|isbn=
Line 178:
A quantum walk is the quantum analogue of a classical [[random walk]]. Similar to a classical random walk, which can be described by a [[probability distribution]] over some states, a quantum walk can be described by a [[quantum superposition]] over states. Quantum walks are known to give exponential speedups for some black-box problems.<ref>
{{cite
|last1=Childs |first1=A. M.
|last2=Cleve |first2=R.
Line 185:
|last5=Gutmann |first5=S.
|last6=Spielman |first6=D. A.
|year=2003
|title=Exponential algorithmic speedup by quantum walk
|doi=10.1145/780542.780552
|class=quant-ph▼
|chapter=Exponential algorithmic speedup by a quantum walk
|isbn=1581136749
|pages=59–68
|volume=35
|issue=2003
|journal=Proc. th ACM Symposium on Theory of Computing (STOC ), pp.
}}</ref><ref>
{{cite
|last1=Childs |first1=A. M.
|last2=Schulman |first2=L. J.
|last3=Vazirani |first3=U. V.
|year=2007
|title=48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
|doi=10.1109/FOCS.2007.18
|chapter=Quantum Algorithms for Hidden Nonlinear Structures
|eprint=0705.2784▼
|isbn=0-7695-3010-9
|pages=395–404
|volume=48
|journal=Proc. th IEEE Symposium on Foundations of Computer Science (FOCS , pp.
}}</ref> They also provide polynomial speedups for many problems. A framework for the creation quantum walk algorithms exists and is quite a versatile tool.<ref name=Search_via_quantum_walk/>
Line 329 ⟶ 340:
|class=quant-ph
|eprint=quant-ph/0506265
|author2=Ashwin Nayak
}}</ref> A quantum algorithm requires <math>\Omega(k^{2/3})</math> queries but the best known algorithm uses <math>O(k^{2/3} \log k)</math> queries.<ref>
{{cite journal
| |||