การเดินแบบควอนตัม (Quantum walk)เป็น อนาล็อก เชิงควอนตัมของการเดินแบบสุ่ม คลาสสิก (Classical random walk) แต่แตกต่างจากการเดินแบบสุ่มคลาสสิกตรงที่ผู้เดินอยู่ในสถานะที่แน่นอน และความสุ่มเกิดขึ้นจากการเปลี่ยนสถานะแบบสุ่ม ในการเดินแบบควอนตัม ความสุ่มเกิดขึ้นจาก:

1. การซ้อนทับเชิงควอนตัมของสถานะ
2. วิวัฒนาการเอกภาพแบบไม่สุ่มและย้อนกลับได้ และ
3. การยุบตัวของฟังก์ชันคลื่นเนื่องจาก การ วัดสถานะ

การเดินแบบควอนตัม (Quantum walks) เป็นเทคนิคสำหรับการสร้างอัลกอริทึมควอนตัม

เช่นเดียวกับการเดินสุ่มแบบคลาสสิก การเดินสุ่มแบบควอนตัมสามารถกำหนดรูปแบบได้ทั้งในเวลาแบบไม่ต่อเนื่องและเวลาแบบต่อเนื่อง

การเดินแบบควอนตัมได้รับแรงบันดาลใจจากการใช้การเดินแบบสุ่มคลาสสิกอย่างแพร่หลายในการออกแบบอัลกอริทึมแบบสุ่ม และเป็นส่วนหนึ่งของอัลกอริทึมควอนตัม หลายอย่าง สำหรับปัญหาการทำนาย บางอย่าง การเดินแบบควอนตัมจะให้ความเร็วที่เพิ่มขึ้นแบบเลขชี้กำลังเมื่อเทียบกับอัลกอริทึมคลาสสิกใดๆ^{[ 1 ] [ 2 ]}การเดินแบบควอนตัมยังให้ ความเร็ว ที่เพิ่มขึ้นแบบพหุนามเมื่อเทียบกับอัลกอริทึมคลาสสิกสำหรับปัญหาในทางปฏิบัติหลายอย่าง เช่นปัญหาความแตกต่างขององค์ประกอบ^{[ 3 ]}ปัญหาการค้นหาสามเหลี่ยม [ ^{4 ] และ}การประเมินต้นไม้ NAND ^{[ 5 ]} อัลกอริทึม การค้นหา Groverที่รู้จักกันดีก็สามารถมองได้ว่าเป็นอัลกอริทึมการเดินแบบควอนตัมเช่นกัน

การเดินควอนตัมแสดงคุณสมบัติที่แตกต่างอย่างมากจากการเดินสุ่มแบบคลาสสิก โดยเฉพาะอย่างยิ่ง การเดินควอนตัมจะไม่ลู่เข้าสู่การกระจายแบบจำกัดและเนื่องจากพลังของการแทรกแซงควอนตัม การเดินควอนตัมอาจแพร่กระจายได้เร็วกว่าหรือช้ากว่าการเดินแบบคลาสสิกอย่างมีนัยสำคัญ นอกจากนี้ยังไม่มีความสุ่มในการเดินควอนตัม เนื่องจากกฎของกลศาสตร์ควอนตัม วิวัฒนาการของระบบควอนตัมที่แยกตัวออกจึงเป็นแบบกำหนดได้ ซึ่งหมายความว่าโดยใช้เงื่อนไขปัจจุบัน คุณสามารถทำนายพฤติกรรมในอนาคตของระบบได้อย่างแม่นยำ ความสุ่มจะเกิดขึ้นในการเดินควอนตัมก็ต่อเมื่อมีการวัดระบบและมีการรวบรวมข้อมูลแบบคลาสสิกเท่านั้น นอกจากนี้ แทนที่จะใช้ "การโยนเหรียญ" ที่ใช้ในระบบคลาสสิก การเดินควอนตัมจะขยายพื้นที่ของระบบทางกายภาพเพื่อสร้างข้อมูลเพิ่มเติม^{[ 6 ]}

การเดินควอนตัมแบบต่อเนื่องเกิดขึ้นเมื่อมีการแทนที่โดเมนเชิงพื้นที่แบบต่อเนื่องในสมการชโรดิงเกอร์ด้วยเซตแบบไม่ต่อเนื่อง กล่าวคือ แทนที่จะให้อนุภาคควอนตัมแพร่กระจายในแบบต่อเนื่อง เราจะจำกัดเซตของสถานะตำแหน่งที่เป็นไปได้ไว้ที่เซตจุดยอดของกราฟบางกราฟ ซึ่งอาจเป็นกราฟจำกัดหรือกราฟอนันต์นับได้ ภายใต้เงื่อนไขบางประการ การเดินควอนตัมแบบต่อเนื่องสามารถเป็นแบบจำลองสำหรับ การคำนวณควอนตัมแบบสากลได้^{[ 7 ]}${\displaystyle V}$${\displaystyle G=(V,E)}$

พิจารณาพลวัตของอนุภาคควอนตัมอิสระไร้สปินที่ไม่เป็นไปตามทฤษฎีสัมพัทธภาพ ซึ่งมีมวลและเคลื่อนที่บนโดเมนเชิงพื้นที่หนึ่งมิติที่ไม่มีที่สิ้นสุด การเคลื่อนที่ของอนุภาคนี้ถูกอธิบายได้อย่างสมบูรณ์โดยฟังก์ชันคลื่นของมันซึ่งสอดคล้องกับสมการชโรดิงเจอร์ของอนุภาคอิสระในหนึ่งมิติ ${\displaystyle m}$${\displaystyle \psi (x,t):\mathbb {R} \times \mathbb {R} _{\geq 0}\to \mathbb {C} }$

${\displaystyle {\textbf {i}}\hbar {\frac {\partial \psi }{\partial t}}=-{\frac {\hbar ^{2}}{2m}}{\frac {\partial ^{2}\psi }{\partial x^{2}}}}$

โดยที่และคือค่าคงที่ของพลังค์ ที่ลดลง สมมติว่าเฉพาะส่วนเชิงพื้นที่ของโดเมนเท่านั้นที่ถูกทำให้เป็นแบบไม่ต่อเนื่อง โดยแทนที่ด้วย โดยที่คือระยะห่างระหว่างตำแหน่งเชิงพื้นที่ที่อนุภาคสามารถครอบครองได้ ฟังก์ชันคลื่นจะกลายเป็นแผนที่และอนุพันธ์ย่อยเชิง พื้นที่อันดับสอง จะกลายเป็นลาปลาเซียนแบบไม่ต่อเนื่อง ${\displaystyle {\textbf {i}}={\sqrt {-1}}}$${\displaystyle \hbar }$${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}}$${\displaystyle \Delta x}$${\displaystyle \psi :\mathbb {Z} _{\Delta x}\times \mathbb {R} _{\geq 0}\to \mathbb {C} }$

${\displaystyle {\frac {\partial ^{2}\psi }{\partial x^{2}}}\to {\frac {L_{\mathbb {Z} }\psi (j\,\Delta x,t)}{\Delta x^{2}}}\equiv {\frac {\psi \left((j+1)\,\Delta x,t\right)-2\psi \left(j\,\Delta x,t\right)+\psi \left((j-1)\,\Delta x,t\right)}{\Delta x^{2}}}}$

ดังนั้น สมการวิวัฒนาการสำหรับการเดินควอนตัมแบบต่อเนื่องในเวลาจึงเป็นดังนี้ ${\displaystyle \mathbb {Z} _{\Delta x}}$

${\displaystyle {\textbf {i}}{\frac {\partial \psi }{\partial t}}=-\omega _{\Delta x}L_{\mathbb {Z} }\psi }$

โดยที่เป็นความถี่ลักษณะเฉพาะ การสร้างนี้สามารถขยายไปสู่กรณีที่โดเมนเชิงพื้นที่แบบไม่ต่อเนื่องเป็นกราฟใดๆและลาปลาเซียนแบบไม่ต่อเนื่องถูกแทนที่ด้วยลาปลาเซียนของกราฟโดยที่และคือเมทริกซ์ดีกรีและเมทริกซ์ประชิดตามลำดับ ตัวเลือกกราฟทั่วไปที่ปรากฏในการศึกษาการเดินควอนตัมแบบต่อเนื่อง ได้แก่แลตทิซd มิติ กราฟวงจรโทริแบบไม่ต่อ เนื่อง d มิติ ไฮเปอร์คิวบ์ dมิติและกราฟสุ่ม ${\displaystyle \omega _{\Delta x}\equiv \hbar /2m\,\Delta x^{2}}$${\displaystyle G=(V,E)}$${\displaystyle L_{\mathbb {Z} }}$${\displaystyle L_{G}\equiv D_{G}-A_{G}}$${\displaystyle D_{G}}$${\displaystyle A_{G}}$${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle \mathbb {Z} /N\mathbb {Z} }$${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{d}}$${\displaystyle \mathbb {Q} ^{d}}$

วิวัฒนาการของการเดินควอนตัมในเวลาแบบไม่ต่อเนื่องถูกกำหนดโดยผลคูณของตัวดำเนินการเอกภาพสองตัว: (1) ตัวดำเนินการ "โยนเหรียญ" และ (2) ตัวดำเนินการเลื่อนแบบมีเงื่อนไข ซึ่งใช้ซ้ำ ๆ ตัวอย่างต่อไปนี้มีประโยชน์^{[ 8 ]}ลองนึกภาพอนุภาคที่มีสปิน 1/2 องศาอิสระที่แพร่กระจายบนอาร์เรย์เชิงเส้นของไซต์แบบไม่ต่อเนื่อง หากจำนวนไซต์ดังกล่าวเป็นอนันต์ที่นับได้ เราจะระบุพื้นที่สถานะด้วยสถานะของอนุภาคสามารถอธิบายได้ด้วยสถานะผลคูณ ${\displaystyle \mathbb {Z} }$

${\displaystyle |\Psi \rangle =|s\rangle \otimes |\psi \rangle }$

ประกอบด้วยสถานะการหมุนภายใน

${\displaystyle |s\rangle \in {\mathcal {H}}_{C}=\left\{a_{\uparrow }|{\uparrow }\rangle +a_{\downarrow }|{\downarrow }\rangle :a_{\uparrow /\downarrow }\in \mathbb {C} \right\}}$

และสถานะตำแหน่ง

${\displaystyle |\psi \rangle \in {\mathcal {H}}_{P}=\left\{\sum _{x\in \mathbb {Z} }\alpha _{x}|x\rangle :\sum _{x\in \mathbb {Z} }|\alpha _{x}|^{2}<\infty \right\}}$

โดยที่"ปริภูมิเหรียญ" และคือปริภูมิของสถานะตำแหน่งควอนตัมทางกายภาพ ผลคูณในบริบทนี้คือผลคูณโครเนกเกอร์ (เทนเซอร์) ตัวดำเนินการเลื่อนแบบมีเงื่อนไขสำหรับการเดินควอนตัมบนเส้นตรงนั้นกำหนดโดย ${\displaystyle {\mathcal {H}}_{C}=\mathbb {C} ^{2}}$${\displaystyle {\mathcal {H}}_{P}=\ell ^{2}(\mathbb {Z} )}$${\displaystyle \otimes }$

${\displaystyle S={\bigl (}|{\uparrow }\rangle \langle {\uparrow }|{\bigr )}\otimes {\Bigl (}\sum \limits _{i}|{i+1}\rangle \langle {i}|{\Bigr )}+{\bigl (}|{\downarrow }\rangle \langle {\downarrow }|{\bigr )}\otimes {\Bigl (}\sum \limits _{i}|{i-1}\rangle \langle {i}|{\Bigr )},}$

กล่าวคือ อนุภาคจะกระโดดไปทางขวาหากมีสปินขึ้น และกระโดดไปทางซ้ายหากมีสปินลง โดยเฉพาะอย่างยิ่ง ตัวดำเนินการเลื่อนแบบมีเงื่อนไขจะกระทำกับสถานะของผลคูณตาม

${\displaystyle S(|{\uparrow }\rangle \otimes |i\rangle )=|{\uparrow }\rangle \otimes |i+1\rangle }$

${\displaystyle S(|{\downarrow }\rangle \otimes |i\rangle )=|{\downarrow }\rangle \otimes |i-1\rangle }$

ถ้าเราหมุนสปินด้วยการแปลงเอกภาพบางอย่างก่อนแล้วจึงใช้เราจะได้การเคลื่อนที่ควอนตัมที่ไม่ธรรมดาบนตัวเลือกที่นิยมสำหรับการแปลงดังกล่าวคือเกตฮาดามาร์ดซึ่งเมื่อเทียบกับฐานสปินส่วนประกอบ z มาตรฐาน จะมีการแสดงเป็นเมทริกซ์${\displaystyle C:{\mathcal {H}}_{C}\to {\mathcal {H}}_{C}}$${\displaystyle S}$${\displaystyle \mathbb {Z} }$${\displaystyle C=H}$

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&\;\;1\\1&-1\end{pmatrix}}}$

เมื่อเลือกตัวเลือกนี้สำหรับตัวดำเนินการโยนเหรียญ ตัวดำเนินการนั้นจะถูกเรียกว่า "เหรียญฮาดามาร์ด" และการเดินควอนตัมที่เกิดขึ้นจะถูกเรียกว่า "การเดินฮาดามาร์ด" หากตัวเดินเริ่มต้นที่จุดกำเนิดและอยู่ในสถานะหมุนขึ้น ขั้นตอนเวลาเดียวของการเดินฮาดามาร์ดจะเป็นดังนี้ ${\displaystyle \mathbb {Z} }$

${\displaystyle |{\uparrow }\rangle \otimes |0\rangle \;\,{\overset {H}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle +|{\downarrow }\rangle )\otimes |0\rangle \;\,{\overset {S}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle \otimes |1\rangle +|{\downarrow }\rangle \otimes |{-1}\rangle ).}$

การวัดสถานะของระบบ ณ จุดนี้จะเผยให้เห็นการหมุนขึ้นที่ตำแหน่ง 1 หรือการหมุนลงที่ตำแหน่ง −1 โดยมีความน่าจะเป็น 1/2 เท่ากัน การทำซ้ำขั้นตอนนี้จะสอดคล้องกับการเดินสุ่มแบบง่ายคลาสสิกบนเพื่อสังเกตการเคลื่อนที่แบบไม่คลาสสิก จะไม่มีการวัดสถานะ ณ จุดนี้ (และดังนั้นจึงไม่บังคับให้ฟังก์ชันคลื่นยุบตัว) แต่ให้ทำซ้ำขั้นตอนการหมุนสปินด้วยตัวดำเนินการโยนเหรียญและกระโดดแบบมีเงื่อนไขด้วย ด้วยวิธีนี้ ความสัมพันธ์ควอนตัมจะยังคงอยู่ และสถานะตำแหน่งที่แตกต่างกันสามารถรบกวนซึ่งกันและกันได้ ซึ่งจะให้การกระจายความน่าจะเป็นที่แตกต่างอย่างมากจากการเดินสุ่มแบบคลาสสิก (การกระจายแบบเกาส์เซียน) ดังที่เห็นในรูปทางด้านขวา ในเชิงพื้นที่จะเห็นว่าการกระจายไม่สมมาตร: แม้ว่าเหรียญ Hadamard จะให้ทั้งสปินขึ้นและลงด้วยความน่าจะเป็นเท่ากัน แต่การกระจายมีแนวโน้มที่จะเลื่อนไปทางขวาเมื่อสปินเริ่มต้นเป็นความไม่สมมาตรนี้เกิดจากข้อเท็จจริงที่ว่าเหรียญ Hadamard ปฏิบัติต่อ สถานะ และอย่างไม่สมมาตร การกระจายความน่าจะเป็นแบบสมมาตรจะเกิดขึ้นหากเลือกสถานะเริ่มต้นเป็น ${\displaystyle \mathbb {Z} }$${\displaystyle S}$${\displaystyle |{\uparrow }\rangle }$${\displaystyle |{\uparrow }\rangle }$${\displaystyle |{\downarrow }\rangle }$

${\displaystyle |\Psi _{0}^{\text{symm}}\rangle ={\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle -{\textbf {i}}|{\downarrow }\rangle )\otimes |0\rangle }$

ลองพิจารณาสิ่งที่เกิดขึ้นเมื่อเราทำให้ตัวดำเนินการ Dirac ที่มีมวลเป็นแบบไม่ต่อเนื่อง ในมิติเชิงพื้นที่ หนึ่งมิติ ในกรณีที่ไม่มีพจน์มวลเราจะมีตัวเคลื่อนที่ไปทางซ้ายและตัวเคลื่อนที่ไปทางขวา ซึ่งสามารถกำหนดลักษณะได้ด้วยระดับความเป็นอิสระ ภายใน "สปิน" หรือ "เหรียญ" เมื่อเราเปิดใช้งานพจน์มวล สิ่งนี้จะสอดคล้องกับการหมุนในปริภูมิ "เหรียญ" ภายในนี้ การเดินควอนตัมสอดคล้องกับการทำซ้ำตัวดำเนินการเลื่อนและตัวดำเนินการเหรียญซ้ำๆ

นี่คล้ายคลึงกับ แบบจำลองของ ริชาร์ด ไฟน์แมนเกี่ยวกับอิเล็กตรอนในมิติเชิงพื้นที่ 1 มิติและมิติเวลา 1 มิติมาก เขาได้สรุปเส้นทางที่คดเคี้ยว โดยส่วนที่เคลื่อนที่ไปทางซ้ายสอดคล้องกับการหมุน (หรือเหรียญ) หนึ่งแบบ และส่วนที่เคลื่อนที่ไปทางขวาสอดคล้องกับการหมุน (หรือเหรียญ) อีกแบบหนึ่ง ดูรายละเอียดเพิ่มเติมได้ ที่กระดานหมากรุกของไฟน์แมน

ความน่าจะเป็นของการเปลี่ยนผ่านสำหรับการเดินควอนตัม 1 มิติมีพฤติกรรมเหมือนฟังก์ชัน Hermiteซึ่ง (1) แกว่งไปมา อย่างไม่สิ้นสุดในบริเวณที่อนุญาตตามแบบคลาสสิก (2) ถูกประมาณโดยฟังก์ชัน Airyรอบกำแพงของศักยภาพ และ (3) ลดลงแบบเอกซ์โพเนนเชียลในบริเวณที่ซ่อนเร้นตามแบบคลาสสิก^{[ 9 ] [ 10 ]}

แนวทางอื่นในการหาปริมาณการเดินสุ่มแบบคลาสสิกคือการใช้ลูกโซ่ Markov แบบเวลาต่อเนื่องซึ่งแตกต่างจากกลไกแบบใช้เหรียญที่ใช้ในการเดินสุ่มแบบเวลาไม่ต่อเนื่องลูกโซ่ Markovไม่จำเป็นต้องอาศัยการโยนเหรียญเพื่อกำหนดทิศทางการเคลื่อนที่^{[ 11 ]}ในกรอบการทำงานนี้ เวลาถือเป็นตัวแปรต่อเนื่อง ทำให้ผู้เดินสามารถเปลี่ยนตำแหน่งระหว่างจุดยอดที่อยู่ติดกันได้ทุกจุดเวลา เมื่อเวลาผ่านไป ความน่าจะเป็นที่จะพบผู้เดินที่จุดยอดข้างเคียงจะเพิ่มขึ้น ในขณะที่ความน่าจะเป็นที่จะยังคงอยู่ที่จุดยอดปัจจุบันจะลดลง อัตราการเปลี่ยนตำแหน่งระหว่างจุดยอดข้างเคียงทำหน้าที่เป็นปัจจัยความน่าจะเป็น แทนที่ความจำเป็นในการโยนเหรียญ^{[ 12 ]}

การเดินควอนตัมบนกราฟอนันต์แสดงถึงพื้นที่การศึกษาที่โดดเด่น ซึ่งมีลักษณะเฉพาะคือการแพร่กระจายที่ไม่จำกัดของการเดินเมื่อเวลาผ่านไป^{[ 13 ]}ในบริบทนี้ ระยะทางที่คาดหวังจากจุดกำเนิดสามารถวัดได้ด้วยค่าเบี่ยงเบนมาตรฐานของการกระจายความน่าจะเป็น การวัดนี้ได้รับการสำรวจบนแลตทิซทั้งแบบหนึ่งมิติและสองมิติ โดยที่ค่าเบี่ยงเบนมาตรฐานจะเพิ่มขึ้นตามสัดส่วนโดยตรงของเวลาวิวัฒนาการ ในทางคลาสสิก ค่าเบี่ยงเบนมาตรฐานของการเดินแบบสุ่มจะเป็นสัดส่วนกับรากที่สองของเวลาวิวัฒนาการ^{[ 12 ]}

โครงสร้างอะตอมเป็นแพลตฟอร์มควอนตัมชั้นนำในแง่ของความสามารถในการปรับขนาด การเดินควอนตัมแบบมีเหรียญและไม่มีเหรียญในเวลาไม่ต่อเนื่องสามารถเกิดขึ้นได้ในโครงสร้างอะตอมผ่านปฏิสัมพันธ์การแลกเปลี่ยนสปินแบบเลือกตามระยะทาง^{[ 14 ]}ที่น่าทึ่งคือแพลตฟอร์มนี้รักษาความสอดคล้องไว้ได้เหนือไซต์และขั้นตอนหลายร้อยรายการใน 1, 2 หรือ 3 มิติในพื้นที่เชิงพื้นที่ ปฏิสัมพันธ์แบบไดโพลระยะไกลช่วยให้สามารถออกแบบเงื่อนไขขอบเขตแบบคาบ ซึ่งอำนวยความสะดวกให้ QW บนพื้นผิวเชิงทอพอโลยี^{[ 14 ]}

• สูตรอินทิกรัลเส้นทาง
• การค้นหาการเดินควอนตัม

• การประชุมเชิงปฏิบัติการระดับนานาชาติว่าด้วยพื้นฐานทางคณิตศาสตร์และฟิสิกส์ของการเดินควอนตัมแบบเวลาไม่ต่อเนื่องเก็บถาวรเมื่อวันที่ 16 ตุลาคม 2018 ที่Wayback Machine
• การเดินควอนตัม
• การนำ Discrete Quantum Walks ไปใช้กับ Classiq