กลับไปหน้าบทความ

อ่าน 3 นาที

การเดินควอนตัมแบบต่อเนื่องตามเวลา

การ เดินควอนตัมแบบต่อเนื่องตามเวลา (CTQW) คือ การเดินควอนตัม บนกราฟ (แบบง่าย) ที่กำหนดโดยเมทริกซ์เอกภาพที่เปลี่ยนแปลงตามเวลาซึ่งอาศัย แฮมิลโทเนียน ของระบบควอนตัมและ เมทริกซ์ประชิด...

การเดินควอนตัมแบบต่อเนื่องตามเวลา

การเดินควอนตัมแบบต่อเนื่องตามเวลา (CTQW)คือการเดินควอนตัมบนกราฟ(แบบง่าย)ที่กำหนดโดยเมทริกซ์เอกภาพที่เปลี่ยนแปลงตามเวลาซึ่งอาศัยแฮมิลโทเนียนของระบบควอนตัมและเมทริกซ์ประชิดแนวคิดของ CTQW เชื่อกันว่าได้รับการพิจารณาครั้งแรกสำหรับการคำนวณควอนตัมโดยEdward Farhiและ Sam Gutmann [ 1 ]เนื่องจากอัลกอริทึมแบบคลาสสิกจำนวนมากมีพื้นฐานมาจากการเดินแบบสุ่ม (แบบคลาสสิก) แนวคิดของ CTQW จึงได้รับการพิจารณาในตอนแรกเพื่อดูว่าจะมีอนาล็อกควอนตัมของอัลกอริทึมเหล่านี้ที่มีเวลาการทำงาน ที่ดี กว่าคู่เทียบแบบคลาสสิกหรือไม่ ในปัจจุบัน ปัญหาต่างๆ เช่น การตัดสินใจว่ากราฟใดมีคุณสมบัติเช่นการถ่ายโอนสถานะที่สมบูรณ์แบบเมื่อเทียบกับ CTQW ของกราฟนั้นได้รับความสนใจเป็นพิเศษ

คำจำกัดความ

สมมติว่าจี{\displaystyle G}เป็นกราฟบนn{\displaystyle n}จุดยอด และว่าทีอาร์{\displaystyle t\in \mathbb {R} }.

การเดินควอนตัมแบบต่อเนื่องตามเวลา

การเดินควอนตัมแบบต่อเนื่องตามเวลายู(ที)เสื่อn×n(ซี){\displaystyle U(t)\in \operatorname {Mat} _{n\times n}(\mathbb {C} )}บนจี{\displaystyle G}ในเวลานั้นที{\displaystyle t}มีนิยามดังนี้:ยู(ที):=อีฉันทีเอ{\displaystyle U(t):=e^{itA}}การปล่อยเอ{\displaystyle A}แทนเมทริกซ์ประชิดของจี{\displaystyle G}.

นอกจากนี้ ยังสามารถกำหนดนิยามการเดินควอนตัมแบบต่อเนื่องในเวลาบน ในลักษณะเดียวกันได้อีกด้วยจี{\displaystyle G}โดยสัมพันธ์กับเมทริกซ์ลาปลาเซียน ของมัน อย่างไรก็ตาม เว้นแต่จะระบุไว้เป็นอย่างอื่น CTQW บนกราฟจะหมายถึง CTQW ที่สัมพันธ์กับเมทริกซ์ประชิดของมันสำหรับส่วนที่เหลือของบทความนี้

เมทริกซ์การผสม

เมทริกซ์การผสมเอ็ม(ที)เสื่อn×n(อาร์){\displaystyle M(t)\in \operatorname {Mat} _{n\times n}(\mathbb {R} )}ของจี{\displaystyle G}ในเวลานั้นที{\displaystyle t}ถูกกำหนดให้เป็นเอ็ม(ที):=ยู(ที)ยู(ที){\displaystyle M(t):=U(t)\circ U(-t)}.

เมทริกซ์การผสมคือเมทริกซ์สมมาตรแบบดับเบิลสโตแคสติกที่ได้มาจาก CTQW บนกราฟ:เอ็ม(ที)คุณ,วี{\displaystyle {M(t)}_{u,v}}ให้ความน่าจะเป็นของคุณ{\displaystyle u}การเปลี่ยนผ่านไปสู่วี{\displaystyle v}ในเวลานั้นที{\displaystyle t}สำหรับจุดยอดใดๆคุณ{\displaystyle u}และ v บนจี{\displaystyle G}.

จุดยอดคาบ

จุดยอดคุณ{\displaystyle u}บนจี{\displaystyle G}กล่าวกันว่าเป็นไปตามช่วงเวลาที{\displaystyle t}ถ้าเอ็ม(ที)คุณ,คุณ=1{\displaystyle {M(t)}_{u,u}=1}.

การโอนสถานะที่สมบูรณ์แบบ

จุดยอดที่แตกต่างกันคุณ{\displaystyle u}และวี{\displaystyle v}บนจี{\displaystyle G}กล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดที{\displaystyle t}ถ้าเอ็ม(ที)คุณ,วี=1{\displaystyle M(t)_{u,v}=1}.

ถ้าจุดยอดคู่หนึ่งบนจี{\displaystyle G}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ณ เวลา t จากนั้นจี{\displaystyle G}กล่าวกันว่าตัวมันเองยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ณ เวลา t)

ชุดหนึ่งเอส{\displaystyle S}คู่ของจุดยอดที่แตกต่างกันบนจี{\displaystyle G}กล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ในเวลา)ที{\displaystyle t}) ถ้าแต่ละคู่ของจุดยอดในเอส{\displaystyle S}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดที{\displaystyle t}.

ชุดหนึ่งเอส{\displaystyle S}ของจุดยอดบนจี{\displaystyle G}กล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ในเวลา)ที{\displaystyle t}) ถ้าสำหรับทั้งหมดคุณเอส{\displaystyle u\in S}มีวีเอส{\displaystyle v\in S}โดยที่คุณ{\displaystyle u}และวี{\displaystyle v}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นที{\displaystyle t}.

กราฟคาบ

กราฟจี{\displaystyle G}กล่าวกันว่าสิ่งนั้นเป็นไปตามช่วงเวลาหากมีเวลาที0{\displaystyle t\neq 0}โดยที่จุดยอดทั้งหมดเป็นคาบที่เวลาที{\displaystyle t}.

กราฟจะเป็นแบบคาบก็ต่อเมื่อค่าลักษณะเฉพาะ (ที่ไม่เป็นศูนย์) ของกราฟ ทั้งหมดเป็นผลคูณเชิงตรรกะของกันและกัน[ 2 ]

นอกจากนี้กราฟปกติจะเป็นกราฟคาบก็ต่อเมื่อเป็นกราฟจำนวนเต็ม เท่านั้น

การโอนสถานะที่สมบูรณ์แบบ

เงื่อนไขที่จำเป็น

ถ้าจุดยอดคู่หนึ่งคุณ{\displaystyle u}และวี{\displaystyle v}บนกราฟจี{\displaystyle G}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นที{\displaystyle t}จากนั้นทั้งสองคุณ{\displaystyle u}และวี{\displaystyle v}เป็นไปตามช่วงเวลา2ที{\displaystyle 2t}[ 3 ]

การถ่ายโอนสถานะที่สมบูรณ์แบบบนผลคูณของกราฟ

พิจารณากราฟจี{\displaystyle G}และชม{\displaystyle H}.

ถ้าทั้งสองจี{\displaystyle G}และชม{\displaystyle H}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นที{\displaystyle t}จากนั้นจึงได้ผลคูณคาร์ทีเซียน ของพวกมันจีชม{\displaystyle G\,\square \,H}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดที{\displaystyle t}.

หากอย่างใดอย่างหนึ่งจี{\displaystyle G}หรือชม{\displaystyle H}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดที{\displaystyle t}จากนั้นการรวมกันที่ไม่ต่อเนื่อง ของพวกเขาจีชม{\displaystyle G\sqcup H}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดที{\displaystyle t}.

การถ่ายโอนสถานะที่สมบูรณ์แบบบนกราฟแบบเดินปกติ

ถ้ากราฟแบบเดินปกติยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ค่าลักษณะเฉพาะทั้งหมดของกราฟนั้นจะเป็นจำนวนเต็ม

ถ้าจี{\displaystyle G}เป็นกราฟในพีชคณิตโคherent เอกพันธุ์ ที่ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ณ เวลาที{\displaystyle t}เช่นกราฟแบบ vertex-transitiveหรือกราฟในassociation schemeแล้วจุดยอดทั้งหมดบนกราฟนั้นจี{\displaystyle G}ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นที{\displaystyle t}นอกจากนี้ กราฟจี{\displaystyle G}จะต้องมีการจับคู่ที่สมบูรณ์แบบซึ่งยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ หากยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบระหว่างจุดยอดที่อยู่ติดกันสองจุด และเป็นกราฟในพีชคณิตที่สอดคล้องกันแบบเอกพันธุ์

กราฟ ปกติที่ส่งผ่านขอบได้จี{\displaystyle G}ไม่สามารถยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบระหว่างจุดยอดที่อยู่ติดกันสองจุดได้ เว้นแต่จะเป็นการรวมกันแบบไม่ทับซ้อนกันของสำเนาของกราฟสมบูรณ์เค2{\displaystyle K_{2}}.

กราฟปกติอย่างเข้มข้นจะยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบได้ก็ต่อเมื่อมันเป็นส่วนเติมเต็มของการรวมกันแบบไม่ทับซ้อนกันของสำเนาจำนวนคู่ของเค2{\displaystyle K_{2}}.

กราฟ ลูกบาศก์ที่มีระยะทางสม่ำเสมอ เพียงกราฟ เดียวที่ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบได้คือกราฟลูกบาศก์

  • CTQW เกี่ยวกับการสาธิต Wolfram
  • การเดินควอนตัม
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Continuous-time_quantum_walk&oldid=1335678272 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ การเดินควอนตัมแบบต่อเนื่องตามเวลา

การ เดินควอนตัมแบบต่อเนื่องตามเวลา (CTQW) คือ การเดินควอนตัม บนกราฟ (แบบง่าย) ที่กำหนดโดยเมทริกซ์เอกภาพที่เปลี่ยนแปลงตามเวลาซึ่งอาศัย แฮมิลโทเนียน ของระบบควอนตัมและ เมทริกซ์ประชิด...

คำจำกัดความ

สมมติว่า จี {\displaystyle G} เป็นกราฟบน n {\displaystyle n} จุดยอด และว่า ที ∈ อาร์ {\displaystyle t\in \mathbb {R} } .

การเดินควอนตัมแบบต่อเนื่องตามเวลา

การเดินควอนตัมแบบต่อเนื่องตามเวลา ยู ( ที ) ∈ เสื่อ n × n ⁡ ( ซี ) {\displaystyle U(t)\in \operatorname {Mat} _{n\times n}(\mathbb {C} )} บน จี {\displaystyle G} ในเวลานั้น ที {\displaystyle t} มีนิยามดังนี้: ยู ( ที ) := อี ฉัน ที เอ {\displaystyle...

เมทริกซ์การผสม

เมทริกซ์การผสม เอ็ม ( ที ) ∈ เสื่อ n × n ⁡ ( อาร์ ) {\displaystyle M(t)\in \operatorname {Mat} _{n\times n}(\mathbb {R} )} ของ จี {\displaystyle G} ในเวลานั้น ที {\displaystyle t} ถูกกำหนดให้เป็น เอ็ม ( ที ) := ยู ( ที ) ∘ ยู ( − ที ) {\displaystyle...