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

ปัญหาดังกล่าวถูกกำหนดไว้ในแบบจำลองความซับซ้อนของต้นไม้ตัดสินใจหรือความซับซ้อนของการสอบถาม และคิดค้นโดยDaniel R. Simonในปี 1994 ^{[ 2 ]} Simon ได้แสดงอัลกอริทึมควอนตัมที่แก้ปัญหาของ Simon ได้เร็วกว่าแบบทวีคูณ โดยใช้การสอบถามน้อยกว่าแบบทวีคูณเมื่อเทียบกับ อัลกอริทึมแบบคลาสสิกเชิง ความน่าจะเป็น (หรือเชิงกำหนด) ที่ดีที่สุด โดยเฉพาะอย่างยิ่ง อัลกอริทึมของ Simon ใช้จำนวนการสอบถามเชิงเส้น และอัลกอริทึมเชิงความน่าจะเป็นแบบคลาสสิกใดๆ ก็ตามจะต้องใช้จำนวนการสอบถามแบบทวีคูณ

ปัญหานี้ทำให้เกิดการแยกออราเคิลระหว่างคลาสความซับซ้อนBPP (ความซับซ้อนของการสอบถามแบบคลาสสิกที่มีข้อผิดพลาดจำกัด) และBQP (ความซับซ้อนของการสอบถามแบบควอนตัมที่มีข้อผิดพลาดจำกัด) ^{[ 3 ]}นี่เป็นการแยกแบบเดียวกันกับที่อัลกอริทึม Bernstein–Vaziraniทำได้ และแตกต่างจากการแยกที่จัดทำโดยอัลกอริทึม Deutsch–Jozsaซึ่งแยกPและEQP ออก จากกัน แตกต่างจากอัลกอริทึม Bernstein–Vazirani การแยกของอัลกอริทึมของ Simon เป็นแบบ เลขชี้กำลัง

เนื่องจากปัญหานี้ถือว่ามีออราเคิล "กล่องดำ" ที่มีโครงสร้างสูงเพื่อบรรลุการเร่งความเร็ว ปัญหานี้จึงมีคุณค่าในทางปฏิบัติเพียงเล็กน้อย^{[ 4 ​​]}อย่างไรก็ตาม หากไม่มีออราเคิลดังกล่าว การเร่งความเร็วแบบเลขชี้กำลังก็พิสูจน์ได้ยาก เนื่องจากจะพิสูจน์ได้ว่าP แตกต่างจากPSPACE

ปัญหาของไซมอนพิจารณาการเข้าถึงฟังก์ชันที่ถูกนำไปใช้โดยกล่องดำหรือออราเคิล ฟังก์ชันนี้รับประกันได้ว่าจะเป็น ฟังก์ชัน แบบหนึ่งต่อหนึ่งหรือฟังก์ชันแบบสองต่อหนึ่ง หากเป็นฟังก์ชันแบบสองต่อหนึ่ง ก็รับประกันได้อีกว่าค่าอินพุตสองค่าคือ และจะมีค่าเท่ากันก็ต่อเมื่อและแตกต่างกันในชุดบิตที่กำหนดไว้ กล่าวคือ ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n}$${\displaystyle f}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle x'}$

ถ้าไม่ใช่ฟังก์ชันหนึ่งต่อหนึ่ง ก็รับประกันได้ว่ามีค่าที่ไม่เป็นศูนย์อยู่ค่าหนึ่งซึ่งสำหรับทุกค่าก็ต่อเมื่อ${\displaystyle f}$${\displaystyle s}$${\displaystyle x\neq x'}$${\displaystyle f(x)=f(x')}$${\displaystyle x'=x\oplus s}$

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

โปรดสังเกตว่า ถ้าแล้วและโดยที่ในทางกลับกัน (เนื่องจาก สำหรับทุกและ) ดังนั้น ปัญหาของไซมอนจึงอาจเขียนใหม่ได้ในรูปแบบต่อไปนี้: ${\displaystyle x'=x}$${\displaystyle f(x')=f(x)}$${\displaystyle x'=x\oplus s}$${\displaystyle s=0}$${\displaystyle a\oplus b\oplus b=a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle x'=x\oplus s\iff x'\oplus x=s}$

เมื่อได้รับสิทธิ์การเข้าถึงแบบกล่องดำหรือแบบออราเคิลไปยังซึ่งสัญญาว่าจะตอบสนอง สำหรับบางและทั้งหมดของก็ต่อเมื่อพิจารณาว่า(เวอร์ชันตัดสินใจ) หรือส่งออก(เวอร์ชันไม่ตัดสินใจ)${\displaystyle f}$${\displaystyle s}$${\displaystyle x,x'}$${\displaystyle f(x)=f(x')}$${\displaystyle x'\oplus x\in \{0,s\}}$${\displaystyle s\neq 0}$${\displaystyle s}$

นอกจากนี้ โปรดสังเกตว่าคำสัญญาดังกล่าวยังบ่งชี้ว่า ถ้าเป็นฟังก์ชันสองต่อหนึ่งแล้ว จะเป็นฟังก์ชันคาบ: ${\displaystyle f}$${\displaystyle f}$${\displaystyle f(x)=f(x\oplus s).}$

ฟังก์ชันต่อไปนี้เป็นตัวอย่างของฟังก์ชันที่ตรงตามคุณสมบัติที่ต้องการ: ${\displaystyle n=3}$

${\displaystyle x}$	${\displaystyle f(x)}$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

ในกรณีนี้(เช่น วิธีแก้ปัญหา) ผลลัพธ์แต่ละอย่างจะเกิดขึ้นสองครั้ง และสตริงอินพุตสองสตริงที่สอดคล้องกับผลลัพธ์ใดๆ ก็ตาม จะมีผลการดำเนินการ XOR ระดับบิตเท่ากับ ${\displaystyle s=110}$${\displaystyle f}$${\displaystyle s=110}$

ตัวอย่างเช่น สตริงอินพุต 010 และ100 ต่างก็ถูกแมป (โดย) ไปยังสตริงเอาต์พุตเดียวกันนั่นคือ 010 และ100 การใช้ XOR กับ 010 และ 100 จะได้ 110 นั่นคือ 110${\displaystyle 010}$${\displaystyle 100}$${\displaystyle f}$${\displaystyle 000}$${\displaystyle {\displaystyle f(010)=000}}$${\displaystyle {\displaystyle f(100)=000}}$${\displaystyle {\displaystyle 010\oplus 100=110=s}.}$

${\displaystyle s=110}$สามารถตรวจสอบได้โดยใช้สตริงอินพุต 001 และ 111 ซึ่งทั้งสองถูกแมป (โดย f) ไปยังสตริงเอาต์พุตเดียวกันคือ 010 การใช้การดำเนินการ XOR กับ 001 และ 111 จะได้ 110 ซึ่งก็คือซึ่งให้ผลลัพธ์เดียวกันกับที่กล่าวมาแล้ว ${\displaystyle 001\oplus 111=110=s}$${\displaystyle s=110}$

ในตัวอย่างนี้ ฟังก์ชันfเป็นฟังก์ชันสองต่อหนึ่งจริง ๆ โดยที่. ${\displaystyle {\displaystyle s\neq 0^{n}}}$

โดยสัญชาตญาณแล้ว นี่เป็นปัญหาที่ยากที่จะแก้ไขด้วยวิธี "แบบคลาสสิก" แม้ว่าจะใช้ความสุ่มและยอมรับความน่าจะเป็นของข้อผิดพลาดเล็กน้อยก็ตาม สัญชาตญาณเบื้องหลังความยากนั้นค่อนข้างง่าย: หากคุณต้องการแก้ปัญหาด้วยวิธีแบบคลาสสิก คุณต้องหาค่าอินพุตสองค่าที่แตกต่างกันและซึ่งไม่มีโครงสร้างใดในฟังก์ชันที่จะช่วยเราหาค่าอินพุตสองค่าดังกล่าวได้ กล่าวคือ เราจะค้นพบบางสิ่งเกี่ยวกับ(หรือสิ่งที่มันทำ) ได้ก็ต่อเมื่อสำหรับค่าอินพุตสองค่าที่แตกต่างกัน เราได้ผลลัพธ์เดียวกัน ในทุกกรณี เราจะต้องเดาค่าอินพุตที่แตกต่างกันก่อนที่จะมีโอกาสพบคู่ที่ให้ผลลัพธ์เดียวกัน เช่นเดียวกับปัญหาวันเกิดเนื่องจากด้วยวิธีคลาสสิก การหา ค่า sด้วยความแน่นอน 100% จะต้องตรวจสอบค่าอินพุต ปัญหาของไซมอนจึงพยายามหาค่าsโดยใช้การสอบถามน้อยกว่าวิธีคลาสสิกนี้ ${\displaystyle x}$${\displaystyle y}$${\displaystyle f(x)=f(y)}$${\displaystyle f}$${\displaystyle f}$${\displaystyle {\displaystyle \โอเมก้า ({\sqrt {2^{n}}})}}$${\displaystyle f}$${\displaystyle {\displaystyle \Theta ({\sqrt {2^{n}}})}}$

โดยรวมแล้ว อัลกอริทึมนี้ใช้ซับรูทีนในการดำเนินการสองขั้นตอนต่อไปนี้:

1. เรียกใช้ซับรูทีนควอนตัมตามจำนวนครั้งที่คาดไว้เพื่อให้ได้รายการสตริงบิตที่เป็นอิสระเชิงเส้น${\displaystyle O(n)}$${\displaystyle y_{1},...,y_{n-1}}$
2. แต่ละค่าตรงตามเงื่อนไขดังนั้นเราจึงสามารถแก้ระบบสมการที่ได้เพื่อให้ได้ค่า${\displaystyle y_{k}}$${\displaystyle y_{k}\cdot s=0}$${\displaystyle s}$

วงจรควอนตัม (ดูภาพประกอบ) คือการนำส่วนควอนตัมของอัลกอริทึมของไซมอนมาใช้งาน ขั้นตอนย่อยควอนตัมของอัลกอริทึมนี้ใช้การแปลงฮาดามาร์ดโดยที่หมาย ถึงการดำเนินการ XOR $${\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }$$${\displaystyle k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}}$${\displaystyle \oplus }$

ขั้นแรก อัลกอริทึมเริ่มต้นด้วยรีจิสเตอร์สองตัว ซึ่งกำหนดค่าเริ่มต้นเป็นจากนั้น เราใช้การแปลง Hadamard กับรีจิสเตอร์ตัวแรก ซึ่งจะให้สถานะ ${\displaystyle |0\rangle ^{\otimes n}|0\rangle ^{\otimes n}}$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.}$

สอบถามข้อมูลจากออราเคิลเพื่อรับสถานะ ${\displaystyle U_{f}}$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle }$.

ใช้การแปลง Hadamard อีกครั้งกับรีจิสเตอร์แรก ซึ่งจะทำให้ได้สถานะดังนี้

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].}$

สุดท้าย เราจะวัดค่ารีจิสเตอร์ตัวแรก (อัลกอริทึมนี้ใช้ได้เช่นกันหากวัดค่ารีจิสเตอร์ตัวที่สองก่อนตัวแรก แต่ไม่จำเป็น) ความน่าจะเป็นของการวัดสถานะคือเนื่องจากการนำขนาดของเวกเตอร์นี้มายกกำลังสอง จะรวมความน่าจะเป็นทั้งหมดของการวัดค่ารีจิสเตอร์ตัวที่สองที่เป็นไปได้ทั้งหมด ซึ่งรีจิสเตอร์ตัวแรกจะต้องมีค่าเท่ากับมีสองกรณีสำหรับการวัดของเรา: ${\displaystyle |j\rangle }$$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}}$$${\displaystyle |j\rangle }$

1. ${\displaystyle s=0^{n}}$และเป็นการเรียนแบบตัวต่อตัว${\displaystyle f}$
2. ${\displaystyle s\neq 0^{n}}$และมีอัตราส่วนสองต่อหนึ่ง${\displaystyle f}$

สำหรับกรณีแรกเนื่องจากในกรณีนี้เป็นฟังก์ชันหนึ่งต่อหนึ่ง ซึ่งหมายความว่าช่วงของคือ นั่นหมายความว่าผลรวมนั้นครอบคลุมเวกเตอร์ฐานทุกตัว สำหรับกรณีที่สอง โปรดสังเกตว่ามีสตริงสองสตริง คือและ ที่ทำให้ โดย ที่ดังนั้นนอกจากนี้เนื่องจากและดังนั้นตอนนี้สามารถประเมินนิพจน์นี้ได้ง่าย โปรดจำไว้ว่าเรากำลังวัดเมื่อแล้วนิพจน์นี้จะประเมินเป็นและเมื่อแล้วนิพจน์นี้จะเป็น $${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}}$$${\displaystyle f}$${\displaystyle f}$${\displaystyle \{0,1\}^{n}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle f(x_{1})=f(x_{2})=z}$${\displaystyle z\in \mathrm {range} (f)}$$${\displaystyle \left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}}$$${\displaystyle x_{1}\oplus x_{2}=s}$${\displaystyle x_{2}=x_{1}\oplus s}$$${\displaystyle {\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}}$$${\displaystyle j}$${\displaystyle j\cdot s=1}$${\displaystyle 0}$${\displaystyle j\cdot s=0}$${\displaystyle 2^{-n+1}}$

ดังนั้น ทั้งในกรณีและกรณีการวัดของเราจึง เป็นไปตามเงื่อนไข${\displaystyle s=0^{n}}$${\displaystyle s\neq 0^{n}}$${\displaystyle j}$${\displaystyle j\cdot s=0}$

เราดำเนินการส่วนควอนตัมของอัลกอริธึมไปเรื่อยๆ จนกว่าเราจะได้รายการสตริงบิตที่เป็นอิสระเชิงเส้นและแต่ละสตริงบิตเป็นไปตามเงื่อนไขดังนั้นเราจึงสามารถแก้ระบบสมการนี้ด้วยวิธีคลาสสิกได้อย่างมีประสิทธิภาพเพื่อหาค่า ${\displaystyle y_{1},\ldots ,y_{n-1}}$${\displaystyle y_{k}}$${\displaystyle y_{k}\cdot s=0}$${\displaystyle s}$

ความน่าจะเป็นที่ตัวแปรสุ่มอิสระเชิงเส้นมีค่าอย่างน้อยเมื่อเราแก้ระบบสมการและได้คำตอบแล้วเราสามารถทดสอบได้ว่าถ้าเป็นจริง เราจะรู้ว่า เนื่องจากถ้าเป็นกรณีที่นั่นหมายความว่าและเนื่องจากเป็นฟังก์ชันหนึ่งต่อหนึ่ง ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$$${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots }$$${\displaystyle s'}$${\displaystyle f(0^{n})=f(s')}$${\displaystyle s'=s}$${\displaystyle f(0^{n})=f(0^{n}\oplus s)=f(s)}$${\displaystyle f(0^{n})\neq f(s')}$${\displaystyle s=0^{n}}$${\displaystyle f(0^{n})\neq f(s')}$${\displaystyle f}$

เราสามารถทำซ้ำอัลกอริทึมของไซมอนได้เป็นจำนวนครั้งคงที่ เพื่อเพิ่มโอกาสความสำเร็จได้ตามต้องการ โดยที่ความซับซ้อนของเวลาจะยังคงเท่าเดิม

พิจารณาตัวอย่างที่ง่ายที่สุดของอัลกอริธึม โดยที่ในกรณีนี้ การเปลี่ยนแปลงสถานะอินพุตผ่านเกต Hadamard และออราเคิลจะส่งผลให้ได้สถานะ (โดยไม่รวมการปรับค่าใหม่): ${\displaystyle n=1}$

${\displaystyle |0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .}$

ถ้านั่นคือแล้วการวัดรีจิสเตอร์ตัวที่สองจะให้ผลลัพธ์เสมอและจะทำให้รีจิสเตอร์ตัวแรกยุบตัวลงสู่สถานะเสมอ (จนกว่าจะมีการปรับค่าใหม่): ${\displaystyle s=1}$${\displaystyle f(0)=f(1)}$${\displaystyle |f(0)\rangle }$

${\displaystyle |0\rangle +|1\rangle .}$

ดังนั้น การใช้ Hadamard และการวัดค่าในรีจิสเตอร์แรกจะให้ผลลัพธ์เป็น เสมอ ในทางกลับกัน ถ้าเป็นฟังก์ชันหนึ่งต่อหนึ่ง นั่นคือแล้วการวัดค่าในรีจิสเตอร์แรกหลังจาก Hadamard ครั้งที่สองอาจให้ผลลัพธ์เป็นและด้วยความน่าจะเป็นเท่ากัน ${\displaystyle |0\rangle }$${\displaystyle f}$${\displaystyle s=0}$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$

เรากู้คืนผลลัพธ์จากการวัดโดยพิจารณาว่าเราวัดค่า เสมอหรือไม่ซึ่งในกรณีนี้หรือเราวัดค่าและด้วยความน่าจะเป็นเท่ากัน ซึ่งในกรณีนี้เราอนุมานได้ว่าวิธีการนี้จะล้มเหลวหากแต่เราก็ยังพบผลลัพธ์ เสมอแต่ความน่าจะเป็นของเหตุการณ์นี้ขึ้นอยู่กับจำนวนการวัดที่ดำเนินการ และสามารถทำให้มีค่าน้อยลงอย่างมากได้โดยการเพิ่มสถิติ ${\displaystyle s}$${\displaystyle |0\rangle }$${\displaystyle s=1}$${\displaystyle |0\rangle }$${\displaystyle |1\rangle }$${\displaystyle s=0}$${\displaystyle s=0}$${\displaystyle |0\rangle }$${\displaystyle 2^{-N}}$${\displaystyle N}$

ลองพิจารณากรณีที่มี ส่วนเริ่มต้นของอัลกอริธึมส่งผลให้ได้สถานะ (ก่อนการปรับค่าใหม่): ถ้าหมายความว่าเป็นฟังก์ชันหนึ่งต่อหนึ่ง การค้นหาบนรีจิสเตอร์ที่สองจะทำให้รีจิสเตอร์แรกยุบตัวลงเป็นสำหรับทุก กล่าวอีกนัยหนึ่ง การใช้เกต Hadamard และการวัดรีจิสเตอร์แรก ทำให้พบ ผลลัพธ์ทั้งสี่ ด้วยความน่าจะเป็นเท่ากัน${\displaystyle n=2}$$${\displaystyle |00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .}$$${\displaystyle s=(00)}$${\displaystyle f}$${\displaystyle |f(x)\rangle }$${\displaystyle |x\rangle }$${\displaystyle x\in \{0,1\}^{2}}$${\displaystyle 00,01,10,11}$

สมมติในทางกลับกันตัวอย่างเช่นการวัดค่าบนรีจิสเตอร์ตัวที่สองจะทำให้รีจิสเตอร์ตัวแรกยุบตัวลงเป็นสถานะและโดยทั่วไปแล้ว การวัดค่าจะให้ค่าบนรีจิสเตอร์ตัวแรก การใช้เกต Hadamard และการวัดค่าบนรีจิสเตอร์ตัวแรกจึงสามารถส่งผลให้เกิดผลลัพธ์และด้วยความน่าจะเป็นที่เท่ากัน ${\displaystyle s\neq (00)}$${\displaystyle s=(01)}$${\displaystyle |f(00)\rangle }$${\displaystyle |00\rangle +|10\rangle }$${\displaystyle |f(xy)\rangle }$${\displaystyle |x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )}$${\displaystyle 00}$${\displaystyle 10}$

เหตุผลที่คล้ายกันนี้สามารถนำไปใช้กับกรณีอื่นๆ ได้เช่นกัน: ถ้าเช่นนั้น ผลลัพธ์ที่เป็นไปได้คือและในขณะที่ถ้าผลลัพธ์ที่เป็นไปได้คือและซึ่งสอดคล้องกับกฎที่กล่าวถึงในกรณีทั่วไป ${\displaystyle s=(10)}$${\displaystyle 00}$${\displaystyle 01}$${\displaystyle s=(11)}$${\displaystyle 00}$${\displaystyle 11}$${\displaystyle j\cdot s=0}$

ดังนั้น ในการกู้คืนข้อมูลเราจึงจำเป็นต้องแยกแยะความแตกต่างระหว่างสี่กรณีนี้ โดยรวบรวมสถิติให้เพียงพอเพื่อให้แน่ใจว่าโอกาสที่จะเข้าใจผิดว่าการกระจายความน่าจะเป็นของผลลัพธ์หนึ่งเป็นการกระจายความน่าจะเป็นของผลลัพธ์อื่นนั้นมีน้อยเพียงพอ ${\displaystyle s}$

อัลกอริทึมของไซมอนต้องการการสอบถามไปยังกล่องดำ ในขณะที่อัลกอริทึมแบบคลาสสิกจะต้องการการสอบถามอย่างน้อย นอกจากนี้ยังเป็นที่ทราบกันว่าอัลกอริทึมของไซมอนเป็นอัลกอริทึมที่เหมาะสมที่สุดในแง่ที่ว่า อัลกอริทึมควอนตัม ใดๆที่ใช้แก้ปัญหานี้ต้องการการสอบถาม^{[ 5 ] [ 6 ]}${\displaystyle O(n)}$${\displaystyle \Omega (2^{n/2})}$${\displaystyle \Omega (n)}$

วงจรควอนตัมที่แสดงในภาพนี้เป็นตัวอย่างง่ายๆ ของวิธีการนำอัลกอริธึมของไซมอนไปใช้ในภาษา Pythonโดยใช้Qiskitซึ่งเป็นเฟรมเวิร์กการพัฒนาซอฟต์แวร์คอมพิวเตอร์ควอนตัมแบบโอเพนซอร์สจาก IBM

• อัลกอริทึม Deutsch–Jozsa
• อัลกอริทึมของชอร์
• อัลกอริธึมเบิร์นสไตน์-วาซิรานี