ใน การคำนวณ ควอนตัมอัลกอริทึมการประมาณเฟสควอนตัมเป็นอัลกอริทึมควอนตัมเพื่อประมาณเฟสที่สอดคล้องกับค่าลักษณะเฉพาะของตัวดำเนินการเอกภาพ ที่กำหนด เนื่องจากค่าลักษณะเฉพาะของตัวดำเนินการเอกภาพจะมี ค่าสัมบูรณ์ เท่ากับหนึ่ง เสมอ จึงสามารถระบุลักษณะเฉพาะได้ด้วยเฟส และด้วยเหตุนี้ อัลกอริทึมจึงสามารถอธิบายได้อย่างเทียบเท่ากับการดึงเฟสหรือค่าลักษณะเฉพาะนั้นเอง อัลกอริทึมนี้ได้รับการแนะนำครั้งแรกโดยAlexei Kitaevในปี 1995 ^{[ 1 ] [ 2 ] : 246}

การประมาณเฟสมักใช้เป็นขั้นตอนย่อยในอัลกอริธึมควอนตัมอื่นๆ เช่นอัลกอริธึมของ Shor [ ^{2 ] : 131} อัลกอริธึมควอนตัมสำหรับระบบสมการเชิงเส้นและ อัลกอริธึมการ ^นับควอนตัม

อัลกอริทึมนี้ทำงานกับชุดคิวบิตสองชุด ซึ่งในบริบทนี้เรียกว่ารีจิสเตอร์ รีจิสเตอร์ทั้งสองประกอบด้วย คิวบิต และตามลำดับ ให้ เป็นตัวดำเนิน การ เอกภาพที่กระทำกับ รี จิ สเตอร์ คิวบิตค่าลักษณะเฉพาะของตัวดำเนินการเอกภาพจะมีค่าสัมบูรณ์เท่ากับหนึ่ง ดังนั้นจึงมีลักษณะเฉพาะด้วยเฟสของมัน ดังนั้นถ้าเป็นเวกเตอร์ลักษณะเฉพาะของแล้วสำหรับบางค่าเนื่องจากความเป็นคาบของเลขชี้กำลังเชิงซ้อน เราจึงสามารถสมมติได้เสมอว่า ${\displaystyle n}$${\displaystyle m}$${\displaystyle U}$${\displaystyle m}$${\displaystyle |\psi \rangle }$${\displaystyle U}$${\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle }$${\displaystyle \theta \in \mathbb {R} }$${\displaystyle 0\leq \theta <1}$

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

กล่าวโดยละเอียด อัลกอริทึมจะส่งคืนค่าประมาณสำหรับด้วยความน่าจะเป็นสูงภายในข้อผิดพลาดแบบบวกโดยใช้คิวบิตในรีจิสเตอร์แรก และ การดำเนินการ ควบคุมUยิ่งไปกว่านั้น เราสามารถปรับปรุงความน่าจะเป็นของความสำเร็จเป็นสำหรับใดๆโดยใช้การใช้งานควบคุม U ทั้งหมดและนี่คือค่าที่เหมาะสมที่สุด^{[ 3 ]}${\displaystyle \theta }$${\displaystyle \varepsilon }$${\displaystyle n=O(\log(1/\varepsilon ))}$${\displaystyle O(1/\varepsilon )}$${\displaystyle 1-\Delta }$${\displaystyle \Delta >0}$${\displaystyle O(\log(1/\Delta )/\varepsilon )}$

สถานะเริ่มต้นของระบบคือ:

${\displaystyle |\Psi _{0}\rangle =|0\rangle ^{\otimes n}|\psi \rangle ,}$

สถานะคิวบิต n ตัวที่วิวัฒนาการผ่าน n คือสถานะใดก่อนอื่นเราใช้การดำเนินการเกต Hadamard คิวบิต n ตัว กับรีจิสเตอร์ตัวแรก ซึ่งสร้างสถานะดังนี้: โปรดสังเกตว่าในที่นี้เรากำลังสลับระหว่างการแสดงแบบไบนารีและ แบบ n -ary สำหรับรีจิสเตอร์คิวบิต n ตัว: เกตทางด้านขวามือเป็นตัวย่อสำหรับสถานะคิวบิต n ตัวโดยที่คือการแยกส่วนไบนารีของ ${\displaystyle |\psi \rangle }$${\displaystyle m}$${\displaystyle U}$${\displaystyle H^{\otimes n}}$$${\displaystyle |\Psi _{1}\rangle =(H^{\otimes n}\otimes I_{m})|\Psi _{0}\rangle ={\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle .}$$${\displaystyle n}$${\displaystyle n}$${\displaystyle |j\rangle }$${\displaystyle n}$${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$${\displaystyle j}$

สถานะนี้จะพัฒนาต่อไปผ่านวิวัฒนาการแบบเอกภาพควบคุมซึ่งการกระทำสามารถเขียนได้ดังนี้สำหรับทุก ๆวิวัฒนาการนี้ยังสามารถเขียนได้อย่างกระชับดังนี้ซึ่งเน้นให้เห็นถึงลักษณะการควบคุม: มันใช้กับรีจิสเตอร์ที่สองโดยมีเงื่อนไขว่ารีจิสเตอร์แรกเป็นเมื่อจำเงื่อนไขค่าลักษณะเฉพาะที่ใช้ได้สำหรับการนำไปใช้กับจึงให้ผลลัพธ์ดังนี้โดยที่เราใช้ ${\displaystyle |\Psi _{1}\rangle }$${\displaystyle U_{C}}$$${\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),}$$${\displaystyle k=0,...,2^{n}-1}$$${\displaystyle U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},}$$${\displaystyle U^{k}}$${\displaystyle |k\rangle }$${\displaystyle |\psi \rangle }$${\displaystyle U_{C}}$${\displaystyle |\Psi _{1}\rangle }$$${\displaystyle |\Psi _{2}\rangle \equiv U_{C}|\Psi _{1}\rangle =\left({\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle \right)\otimes |\psi \rangle ,}$$${\displaystyle U^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$

เพื่อแสดงให้เห็นว่าสามารถนำไปใช้ได้อย่างมีประสิทธิภาพเช่นกัน สังเกตว่าเราสามารถเขียนได้ว่า โดยที่แทนการดำเนินการของการประยุกต์ใช้กับรีจิสเตอร์ที่สองโดยมีเงื่อนไขว่าคิวบิตที่ ของรีจิสเตอร์แรกเป็น ใน ทางรูปธรรม เกตเหล่านี้สามารถกำหนดลักษณะได้ด้วยการกระทำดังนี้สมการนี้สามารถตีความได้ว่าสถานะจะไม่เปลี่ยนแปลงเมื่อนั่นคือเมื่อคิวบิตที่ เป็นในขณะที่เกตจะถูกนำไปใช้กับรีจิสเตอร์ที่สองเมื่อคิวบิตที่ เป็นการประกอบของเกตควบคุมเหล่านี้จึงให้โดยขั้นตอนสุดท้ายเป็นผลโดยตรงจากการแยกส่วนแบบไบนารี ${\displaystyle U_{C}}$${\displaystyle U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})}$${\displaystyle C_{\ell }(U^{2^{\ell }})}$${\displaystyle U^{2^{\ell }}}$${\displaystyle \ell }$${\displaystyle |1\rangle }$$${\displaystyle C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \rangle ).}$$${\displaystyle j_{\ell }=0}$${\displaystyle \ell }$${\displaystyle |0\rangle }$${\displaystyle U^{k}}$${\displaystyle \ell }$${\displaystyle |1\rangle }$$${\displaystyle \prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes \left(U^{\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}|\psi \rangle \right)=U_{C}\left(|j\rangle \otimes |\psi \rangle \right),}$$${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$

จากจุดนี้เป็นต้นไป รีจิสเตอร์ตัวที่สองจะไม่ถูกแตะต้อง ดังนั้นจึงสะดวกที่จะเขียนโดยใช้สถานะของรีจิสเตอร์คิวบิต ซึ่งเป็นรีจิสเตอร์เดียวที่เราต้องพิจารณาสำหรับส่วนที่เหลือของอัลกอริธึม ${\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle }$${\displaystyle |{\tilde {\Psi }}_{2}\rangle }$${\displaystyle n}$

ส่วนสุดท้ายของวงจรเกี่ยวข้องกับการประยุกต์ใช้การแปลงฟูริเยร์ควอนตัม ผกผัน (QFT) กับรีจิสเตอร์แรกของ: QFT และการแปลงผกผันของมันมีลักษณะเฉพาะโดยการกระทำต่อสถานะพื้นฐานดังนี้ ดังนั้นจึงสรุปได้ว่า ${\displaystyle {\mathcal {QFT}}}$${\displaystyle |\Psi _{2}\rangle }$$${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\tilde {\Psi }}_{2}\rangle .}$$$${\displaystyle {\begin{aligned}{\mathcal {QFT}}_{N}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{{\frac {2\pi i}{N}}jk}|j\rangle ,\\{\mathcal {QFT}}_{N}^{-1}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{-{\frac {2\pi i}{N}}jk}|j\rangle .\end{aligned}}}$$

${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .}$

การแยกส่วนสถานะในฐานการคำนวณเป็นสัมประสิทธิ์จึงเท่ากับโดยที่เราเขียนว่า โดยที่คือจำนวนเต็มที่ใกล้เคียงที่สุด กับ ผลต่าง ต้องเป็นไปตามนิยามซึ่งเท่ากับการประมาณค่าของโดยการปัดเศษ ให้ เป็นจำนวนเต็มที่ใกล้เคียงที่สุด ${\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$$${\displaystyle c_{x}\equiv {\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}(x-2^{n}\theta )}={\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k},}$$${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$${\displaystyle a}$${\displaystyle 2^{n}\theta }$${\displaystyle 2^{n}\delta }$${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$${\displaystyle \theta \in [0,1]}$${\displaystyle 2^{n}\theta }$

ขั้นตอนสุดท้ายเกี่ยวข้องกับการทำการวัดในฐานการคำนวณบนรีจิสเตอร์แรก ซึ่งจะให้ผลลัพธ์ที่มีความน่าจะเป็นดังนั้นถ้านั่นคือ เมื่อสามารถเขียนได้เป็นเราจะพบผลลัพธ์เสมอในทางกลับกัน ถ้าความน่าจะเป็นจะเป็นจากนิพจน์นี้เราจะเห็นว่าเมื่อเพื่อดูสิ่งนี้ เราสังเกตว่าจากนิยามของเรามีความไม่เท่าเทียมกันและดังนั้น: ^{[ 4 ] : 157 [ 5 ] : 348} ${\displaystyle |y\rangle }$$${\displaystyle \Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.}$$${\displaystyle \operatorname {Pr} (a)=1}$${\displaystyle \delta =0}$${\displaystyle \theta }$${\displaystyle \theta =a/2^{n}}$${\displaystyle y=a}$${\displaystyle \delta \neq 0}$$${\displaystyle \operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.}$$${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$${\displaystyle \delta \neq 0}$${\displaystyle \delta }$${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$$${\displaystyle {\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |\\&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}}$$

เราสรุปได้ว่าอัลกอริทึมนี้ให้ค่าประมาณบิตที่ดีที่สุด (กล่าวคือ ค่าที่อยู่ภายในคำตอบที่ถูกต้อง) ของด้วยความน่าจะเป็นอย่างน้อยโดยการเพิ่มคิวบิตพิเศษจำนวนหนึ่งตามลำดับของและตัดคิวบิตพิเศษเหล่านั้น ความน่าจะเป็นสามารถเพิ่มขึ้นเป็น^{[ 5 ]}${\displaystyle n}$${\displaystyle 1/2^{n}}$${\displaystyle \theta }$${\displaystyle 4/\pi ^{2}}$${\displaystyle O(\log(1/\epsilon ))}$${\displaystyle 1-\epsilon }$

พิจารณาตัวอย่างที่ง่ายที่สุดของอัลกอริธึม ซึ่งเกี่ยวข้อง เฉพาะ คิวบิตเดียว นอกเหนือจากคิวบิตที่จำเป็นสำหรับการเข้ารหัส สมมติว่าค่าไอเก นของคือ ส่วนแรกของอัลกอริธึมสร้างสถานะคิวบิตเดียวการใช้ควอนตัมฟิลด์ผกผันในกรณีนี้เทียบเท่ากับการใช้เกตฮาดามาร์ดดังนั้นความน่าจะเป็นของผลลัพธ์สุดท้ายคือ โดยที่หรือกล่าวให้ชัดเจนยิ่งขึ้นสมมติว่าหมายถึงแล้ว และเราจะได้ค่าที่แน่นอนของ จากผลลัพธ์การวัดอย่างแน่นอน เช่นเดียวกันนี้ใช้ได้ หาก ${\displaystyle n=1}$${\displaystyle |\psi \rangle }$${\displaystyle |\psi \rangle }$${\displaystyle \lambda =e^{2\pi i\theta }}$${\displaystyle \theta \in [0,1)}$${\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )}$${\displaystyle p_{\pm }=|\langle \pm |\phi \rangle |^{2}}$${\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )}$$${\displaystyle p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.}$$${\displaystyle \lambda =1}$${\displaystyle |\phi \rangle =|+\rangle }$${\displaystyle p_{+}=1}$${\displaystyle p_{-}=0}$${\displaystyle \lambda }$${\displaystyle \lambda =-1}$

ในทางกลับกัน ถ้านั่นคือและในกรณีนี้ ผลลัพธ์จะไม่แน่นอน แต่เราก็ยังพบว่าผลลัพธ์นี้มีโอกาสเกิดขึ้นมากกว่า ซึ่งสอดคล้องกับข้อเท็จจริงที่ว่ามีค่าใกล้เคียง 1 มากกว่า 0 ${\displaystyle \lambda =e^{2\pi i/3}}$${\displaystyle p_{\pm }=[1\pm \cos(2\pi /3)]/2}$${\displaystyle p_{+}=1/4}$${\displaystyle p_{-}=3/4}$${\displaystyle |-\rangle }$${\displaystyle 2/3}$

โดยทั่วไปแล้ว ถ้าแล้วก็ต่อเมื่อ เท่านั้นซึ่งสอดคล้องกับผลลัพธ์ข้างต้น เพราะในกรณีที่ ซึ่งสอดคล้องกับเฟสจะถูกดึงกลับมาได้อย่างแน่นอน และเฟสอื่นๆ จะถูกดึงกลับมาด้วยความแม่นยำที่สูงขึ้น ยิ่งอยู่ใกล้กับสองเฟสนี้มากเท่าไหร่ ${\displaystyle \lambda =e^{2\pi i\theta }}$${\displaystyle p_{+}\geq 1/2}$${\displaystyle |\theta |\leq 1/4}$${\displaystyle \lambda =\pm 1}$${\displaystyle \theta =0,1/2}$

• อัลกอริทึมของชอร์
• อัลกอริทึมการนับควอนตัม
• การวัดความเท่าเทียมกัน