การเดินควอนตัมแบบต่อเนื่องตามเวลา
การเดินควอนตัมแบบต่อเนื่องตามเวลา (CTQW)คือการเดินควอนตัมบนกราฟ(แบบง่าย)ที่กำหนดโดยเมทริกซ์เอกภาพที่เปลี่ยนแปลงตามเวลาซึ่งอาศัยแฮมิลโทเนียนของระบบควอนตัมและเมทริกซ์ประชิดแนวคิดของ CTQW เชื่อกันว่าได้รับการพิจารณาครั้งแรกสำหรับการคำนวณควอนตัมโดยEdward Farhiและ Sam Gutmann [ 1 ]เนื่องจากอัลกอริทึมแบบคลาสสิกจำนวนมากมีพื้นฐานมาจากการเดินแบบสุ่ม (แบบคลาสสิก) แนวคิดของ CTQW จึงได้รับการพิจารณาในตอนแรกเพื่อดูว่าจะมีอนาล็อกควอนตัมของอัลกอริทึมเหล่านี้ที่มีเวลาการทำงาน ที่ดี กว่าคู่เทียบแบบคลาสสิกหรือไม่ ในปัจจุบัน ปัญหาต่างๆ เช่น การตัดสินใจว่ากราฟใดมีคุณสมบัติเช่นการถ่ายโอนสถานะที่สมบูรณ์แบบเมื่อเทียบกับ CTQW ของกราฟนั้นได้รับความสนใจเป็นพิเศษ
คำจำกัดความ
สมมติว่าเป็นกราฟบนจุดยอด และว่า.
การเดินควอนตัมแบบต่อเนื่องตามเวลา
การเดินควอนตัมแบบต่อเนื่องตามเวลาบนในเวลานั้นมีนิยามดังนี้:การปล่อยแทนเมทริกซ์ประชิดของ.
นอกจากนี้ ยังสามารถกำหนดนิยามการเดินควอนตัมแบบต่อเนื่องในเวลาบน ในลักษณะเดียวกันได้อีกด้วยโดยสัมพันธ์กับเมทริกซ์ลาปลาเซียน ของมัน อย่างไรก็ตาม เว้นแต่จะระบุไว้เป็นอย่างอื่น CTQW บนกราฟจะหมายถึง CTQW ที่สัมพันธ์กับเมทริกซ์ประชิดของมันสำหรับส่วนที่เหลือของบทความนี้
เมทริกซ์การผสม
เมทริกซ์การผสมของในเวลานั้นถูกกำหนดให้เป็น.
เมทริกซ์การผสมคือเมทริกซ์สมมาตรแบบดับเบิลสโตแคสติกที่ได้มาจาก CTQW บนกราฟ:ให้ความน่าจะเป็นของการเปลี่ยนผ่านไปสู่ในเวลานั้นสำหรับจุดยอดใดๆและ v บน.
จุดยอดคาบ
จุดยอดบนกล่าวกันว่าเป็นไปตามช่วงเวลาถ้า.
การโอนสถานะที่สมบูรณ์แบบ
จุดยอดที่แตกต่างกันและบนกล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดถ้า.
ถ้าจุดยอดคู่หนึ่งบนยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ณ เวลา t จากนั้นกล่าวกันว่าตัวมันเองยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ณ เวลา t)
ชุดหนึ่งคู่ของจุดยอดที่แตกต่างกันบนกล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ในเวลา)) ถ้าแต่ละคู่ของจุดยอดในยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนด.
ชุดหนึ่งของจุดยอดบนกล่าวกันว่ายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ (ในเวลา)) ถ้าสำหรับทั้งหมดมีโดยที่และยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้น.
กราฟคาบ
กราฟกล่าวกันว่าสิ่งนั้นเป็นไปตามช่วงเวลาหากมีเวลาโดยที่จุดยอดทั้งหมดเป็นคาบที่เวลา.
กราฟจะเป็นแบบคาบก็ต่อเมื่อค่าลักษณะเฉพาะ (ที่ไม่เป็นศูนย์) ของกราฟ ทั้งหมดเป็นผลคูณเชิงตรรกะของกันและกัน[ 2 ]
นอกจากนี้กราฟปกติจะเป็นกราฟคาบก็ต่อเมื่อเป็นกราฟจำนวนเต็ม เท่านั้น
การโอนสถานะที่สมบูรณ์แบบ
เงื่อนไขที่จำเป็น
ถ้าจุดยอดคู่หนึ่งและบนกราฟยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นจากนั้นทั้งสองและเป็นไปตามช่วงเวลา[ 3 ]
การถ่ายโอนสถานะที่สมบูรณ์แบบบนผลคูณของกราฟ
พิจารณากราฟและ.
ถ้าทั้งสองและยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นจากนั้นจึงได้ผลคูณคาร์ทีเซียน ของพวกมันยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนด.
หากอย่างใดอย่างหนึ่งหรือยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนดจากนั้นการรวมกันที่ไม่ต่อเนื่อง ของพวกเขายอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลาที่กำหนด.
การถ่ายโอนสถานะที่สมบูรณ์แบบบนกราฟแบบเดินปกติ
ถ้ากราฟแบบเดินปกติยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ค่าลักษณะเฉพาะทั้งหมดของกราฟนั้นจะเป็นจำนวนเต็ม
ถ้าเป็นกราฟในพีชคณิตโคherent เอกพันธุ์ ที่ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ ณ เวลาเช่นกราฟแบบ vertex-transitiveหรือกราฟในassociation schemeแล้วจุดยอดทั้งหมดบนกราฟนั้นยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบในเวลานั้นนอกจากนี้ กราฟจะต้องมีการจับคู่ที่สมบูรณ์แบบซึ่งยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบ หากยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบระหว่างจุดยอดที่อยู่ติดกันสองจุด และเป็นกราฟในพีชคณิตที่สอดคล้องกันแบบเอกพันธุ์
กราฟ ปกติที่ส่งผ่านขอบได้ไม่สามารถยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบระหว่างจุดยอดที่อยู่ติดกันสองจุดได้ เว้นแต่จะเป็นการรวมกันแบบไม่ทับซ้อนกันของสำเนาของกราฟสมบูรณ์.
กราฟปกติอย่างเข้มข้นจะยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบได้ก็ต่อเมื่อมันเป็นส่วนเติมเต็มของการรวมกันแบบไม่ทับซ้อนกันของสำเนาจำนวนคู่ของ.
กราฟ ลูกบาศก์ที่มีระยะทางสม่ำเสมอ เพียงกราฟ เดียวที่ยอมรับการถ่ายโอนสถานะที่สมบูรณ์แบบได้คือกราฟลูกบาศก์
ลิงก์ภายนอก
- CTQW เกี่ยวกับการสาธิต Wolfram
- การเดินควอนตัม