อัลกอริทึมของ Simon

อัลกอริทึมของ Simon คืออัลกอริทึม query เชิงควอนตัมสำหรับปัญหาที่เรียกว่า ปัญหาของ Simon นี่เป็น promise problem ที่มีรสชาติคล้ายกับปัญหา Deutsch-Jozsa และ Bernstein-Vazirani แต่มีรายละเอียดที่แตกต่างกัน

อัลกอริทึมของ Simon มีความสำคัญเพราะให้ข้อได้เปรียบแบบ exponential ของควอนตัมเหนืออัลกอริทึมคลาสสิก (รวมถึง probabilistic) และเทคนิคที่ใช้เป็นแรงบันดาลใจให้ Peter Shor ค้นพบอัลกอริทึมควอนตัมที่มีประสิทธิภาพสำหรับการแยกตัวประกอบจำนวนเต็ม

ปัญหาของ Simon

ฟังก์ชันอินพุตสำหรับปัญหาของ Simon อยู่ในรูปแบบ

$$f:\Sigma^n \rightarrow \Sigma^m$$

สำหรับจำนวนเต็มบวก $n$ และ $m$ เราอาจจำกัดความสนใจไว้ที่กรณี $m = n$ เพื่อความเรียบง่าย แต่ไม่ได้ให้ประโยชน์มากในการตั้งสมมติฐานนี้ — อัลกอริทึมของ Simon และการวิเคราะห์ก็เหมือนกันไม่ว่าจะเป็นแบบใด

ปัญหาของ Simon

อินพุต: ฟังก์ชัน $f:\Sigma^n \rightarrow \Sigma^m$
Promise: มีสตริง $s\in\Sigma^n$ ที่ $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ สำหรับทุก $x,y\in\Sigma^n$
เอาต์พุต: สตริง $s$

เราจะอธิบาย promise อย่างละเอียดเพื่อทำความเข้าใจสิ่งที่มันบอกในไม่ช้า แต่ก่อนอื่นขอยืนยันว่ามันกำหนดให้ $f$ มีโครงสร้างพิเศษมาก — ดังนั้นฟังก์ชันส่วนใหญ่จะไม่ตอบสนอง promise นี้ นอกจากนี้ยังเหมาะสมที่จะรับรู้ว่าปัญหานี้ไม่ได้มีความสำคัญในทางปฏิบัติ แต่มันเป็นปัญหาที่ถูกสร้างขึ้นอย่างประดิษฐ์บางส่วน ออกแบบมาเพื่อให้คอมพิวเตอร์ควอนตัมทำได้ง่ายและคอมพิวเตอร์คลาสสิกทำได้ยาก

มีสองกรณีหลัก: กรณีแรกคือ $s$ เป็นสตริงที่มีแต่ศูนย์ $0^n$ และกรณีที่สองคือ $s$ ไม่ใช่สตริงที่มีแต่ศูนย์

• กรณีที่ 1: $s=0^n$ ถ้า $s$ เป็นสตริงที่มีแต่ศูนย์ เราสามารถลดรูปข้อความ if and only if ใน promise เพื่อให้อ่านว่า $[f(x) = f(y)] \Leftrightarrow [x = y]$ ซึ่งเทียบเท่ากับ $f$ เป็นฟังก์ชันแบบ one-to-one

• กรณีที่ 2: $s\neq 0^n$ ถ้า $s$ ไม่ใช่สตริงที่มีแต่ศูนย์ promise ที่ถูกตอบสนองสำหรับสตริงนี้บ่งชี้ว่า $f$ เป็น two-to-one หมายความว่าสำหรับทุกสตริงเอาต์พุตที่เป็นไปได้ของ $f$ มีสตริงอินพุตสองตัวที่ทำให้ $f$ แสดงผลสตริงนั้น นอกจากนี้ สองสตริงอินพุตนี้ต้องอยู่ในรูปแบบ $w$ และ $w \oplus s$ สำหรับสตริงบางตัว $w$

สำคัญมากที่ต้องตระหนักว่ามีเพียงสตริง $s$ เดียวที่ใช้ได้ถ้า promise ถูกปฏิบัติตาม ดังนั้นจึงมีคำตอบที่ถูกต้องเพียงหนึ่งเดียวสำหรับฟังก์ชันที่ตอบสนอง promise เสมอ

นี่คือตัวอย่างของฟังก์ชันในรูปแบบ $f:\Sigma^3 \rightarrow \Sigma^5$ ที่ตอบสนอง promise สำหรับสตริง $s = 011$

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

มีสตริงอินพุต $8$ ตัวและสตริงเอาต์พุตที่แตกต่างกัน $4$ ตัว แต่ละตัวปรากฏสองครั้ง — ดังนั้นนี่คือฟังก์ชัน two-to-one นอกจากนี้ สำหรับสตริงอินพุตที่แตกต่างกันสองตัวใด ๆ ที่ให้สตริงเอาต์พุตเดิม เราจะเห็นว่า bitwise XOR ของสตริงอินพุตทั้งสองเท่ากับ $011$ ซึ่งเทียบเท่ากับการบอกว่าสตริงใดสตริงหนึ่งเท่ากับอีกสตริงที่ XOR กับ $s$

สังเกตว่าสิ่งเดียวที่สำคัญเกี่ยวกับสตริงเอาต์พุตจริง ๆ คือว่าพวกมันเหมือนกันหรือแตกต่างกันสำหรับทางเลือกอินพุตที่แตกต่างกัน ตัวอย่างเช่น ในตัวอย่างข้างต้น มีสี่สตริง $(10011,$ $00101,$ $00001,$ และ $11010)$ ที่ปรากฏเป็นเอาต์พุตของ $f$ เราสามารถแทนที่สี่สตริงเหล่านี้ด้วยสตริงที่แตกต่างกัน ตราบใดที่พวกมันทั้งหมดแตกต่างกัน และคำตอบที่ถูกต้อง $s = 011$ จะไม่เปลี่ยนแปลง

คำอธิบายอัลกอริทึม

นี่คือแผนภาพวงจรควอนตัมที่แสดงอัลกอริทึมของ Simon

ชัดเจนว่ามี $n$ Qubit อยู่ด้านบนที่ถูกกระทำโดย Hadamard Gate และ $m$ Qubit อยู่ด้านล่างที่เข้าสู่ query gate โดยตรง มันดูคล้ายมากกับอัลกอริทึมที่เราพูดถึงแล้วในบทเรียน แต่คราวนี้ไม่มี phase kickback; $m$ Qubit ล่างทั้งหมดเข้าสู่ query gate ในสถานะ $\vert 0\rangle$

การแก้ปัญหาของ Simon โดยใช้วงจรนี้จะต้องใช้หลายรอบอิสระตามด้วยขั้นตอนการประมวลผลหลังคลาสสิก ซึ่งจะอธิบายในภายหลังหลังจากวิเคราะห์พฤติกรรมของวงจรแล้ว

การวิเคราะห์

การวิเคราะห์อัลกอริทึมของ Simon เริ่มต้นในแนวทางที่คล้ายกับอัลกอริทึม Deutsch-Jozsa หลังจาก Hadamard Gate ชั้นแรกถูกดำเนินการบน $n$ Qubit บน สถานะกลายเป็น

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

เมื่อดำเนินการ $U_f$ เอาต์พุตของฟังก์ชัน $f$ จะถูก XOR เข้ากับสถานะที่มีแต่ศูนย์ของ $m$ Qubit ล่าง ดังนั้นสถานะกลายเป็น

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

เมื่อดำเนินการ Hadamard Gate ชั้นที่สอง เราได้สถานะต่อไปนี้โดยใช้สูตรเดิมสำหรับการกระทำของ Hadamard Gate ชั้นหนึ่ง

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

ณ จุดนี้ การวิเคราะห์แยกออกจากการวิเคราะห์ของอัลกอริทึมก่อนหน้าในบทเรียนนี้

เราสนใจความน่าจะเป็นที่การวัดจะได้ผลเป็นแต่ละสตริง $y\in\Sigma^n$ ที่เป็นไปได้ ผ่านกฎสำหรับการวิเคราะห์การวัดที่อธิบายในบทเรียน ระบบหลายระบบ ของคอร์ส พื้นฐานของข้อมูลเชิงควอนตัม เราพบว่าความน่าจะเป็น $p(y)$ ในการได้สตริง $y$ เท่ากับ

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

เพื่อให้เข้าใจความน่าจะเป็นเหล่านี้ได้ดีขึ้น เราจำเป็นต้องมีสัญลักษณ์และคำศัพท์เพิ่มเติมเล็กน้อย ก่อนอื่น range ของฟังก์ชัน $f$ คือเซตที่มีสตริงเอาต์พุตทั้งหมด

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

ประการที่สอง สำหรับแต่ละสตริง $z\in\operatorname{range}(f)$ เราสามารถแสดงเซตของสตริงอินพุตทั้งหมดที่ทำให้ฟังก์ชันประเมินค่าเป็นสตริงเอาต์พุต $z$ นี้ว่า $f^{-1}(\{z\})$

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

เซต $f^{-1}(\{z\})$ เรียกว่า preimage ของ $\{z\}$ ภายใต้ $f$ เราสามารถนิยาม preimage ภายใต้ $f$ ของเซตใด ๆ แทนที่ $\{z\}$ ในลักษณะเดียวกัน — มันคือเซตของทุกสมาชิกที่ $f$ แมปไปยังเซตนั้น (สัญลักษณ์นี้ไม่ควรสับสนกับ ฟังก์ชันผกผัน ของ $f$ ซึ่งอาจไม่มีอยู่ ข้อเท็จจริงที่ว่าอาร์กิวเมนต์ทางด้านซ้ายคือเซต $\{z\}$ แทนที่จะเป็นสมาชิก $z$ คือสัญญาณที่ช่วยให้เราหลีกเลี่ยงความสับสนนี้)

โดยใช้สัญลักษณ์นี้ เราสามารถแยกผลรวมในนิพจน์ของความน่าจะเป็นข้างต้น เพื่อได้

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

ทุกสตริง $x\in\Sigma^n$ ถูกแทนด้วยผลรวมสองชั้นอย่างละหนึ่งครั้งอย่างแม่นยำ — โดยพื้นฐานแล้วเราแค่วางสตริงเหล่านี้ลงในถังแยกกันขึ้นอยู่กับว่าสตริงเอาต์พุต $z = f(x)$ ใดที่พวกมันสร้างเมื่อเราประเมินฟังก์ชัน $f$ แล้วรวมแยกกันในแต่ละถัง

เราสามารถประเมิน Euclidean norm กำลังสองเพื่อได้

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

เพื่อลดรูปความน่าจะเป็นเหล่านี้ต่อไป มาดูค่า

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

สำหรับการเลือก $z\in\operatorname{range}(f)$ ใด ๆ

ถ้า $s = 0^n$ ดังนั้น $f$ เป็นฟังก์ชัน one-to-one และมีเพียงสมาชิกเดียว $x\in f^{-1}(\{z\})$ สำหรับทุก $z\in\operatorname{range}(f)$ ค่าของนิพจน์ $(1)$ คือ $1$ ในกรณีนี้

ในทางกลับกัน ถ้า $s\neq 0^n$ ดังนั้นมีสตริงสองตัวในเซต $f^{-1}(\{z\})$ อย่างแน่นอน พูดอย่างเจาะจง ถ้าเราเลือก $w\in f^{-1}(\{z\})$ เป็นหนึ่งในสองสตริงนี้ ดังนั้นอีกสตริงต้องเป็น $w \oplus s$ ตาม promise ในปัญหาของ Simon โดยใช้การสังเกตนี้ เราสามารถลดรูป $(1)$ ได้ดังนี้

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

ดังนั้น ปรากฏว่าค่า $(1)$ ไม่ขึ้นอยู่กับการเลือก $z\in\operatorname{range}(f)$ เฉพาะในทั้งสองกรณี

ตอนนี้เราสามารถเสร็จสิ้นการวิเคราะห์โดยพิจารณาสองกรณีเดิมแยกกัน

• กรณีที่ 1: $s = 0^n$ ในกรณีนี้ฟังก์ชัน $f$ เป็น one-to-one ดังนั้นมีสตริง $z\in\operatorname{range}(f)$ จำนวน $2^n$ ตัว และเราได้

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  กล่าวอีกนัยหนึ่ง การวัดให้สตริง $y\in\Sigma^n$ ที่เลือกแบบ uniform random

• กรณีที่ 2: $s \neq 0^n$ ในกรณีนี้ $f$ เป็น two-to-one ดังนั้นมีสมาชิก $2^{n-1}$ ตัวใน $\operatorname{range}(f)$ โดยใช้สูตรข้างต้น เราสรุปได้ว่าความน่าจะเป็นในการวัดแต่ละ $y\in\Sigma^n$ คือ

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  กล่าวอีกนัยหนึ่ง เราได้สตริงที่เลือกแบบ uniform random จากเซต $\{y\in\Sigma^n : y \cdot s = 0\}$ ซึ่ง มีสตริง $2^{n-1}$ ตัว (เพราะ $s\neq 0^n$ ครึ่งหนึ่งของสตริงไบนารีความยาว $n$ มี binary dot product เป็น $1$ กับ $s$ และอีกครึ่งหนึ่งมี binary dot product เป็น $0$ กับ $s$ ดังที่เราสังเกตแล้วในการวิเคราะห์ อัลกอริทึม Deutsch-Jozsa สำหรับปัญหา Bernstein-Vazirani)

การประมวลผลหลังคลาสสิก

ตอนนี้เรารู้แล้วว่าความน่าจะเป็นเป็นอย่างไรสำหรับผลการวัดที่เป็นไปได้เมื่อเรารันวงจรควอนตัมสำหรับอัลกอริทึมของ Simon ข้อมูลนี้เพียงพอที่จะหาค่า $s$ หรือไม่?

คำตอบคือใช่ ตราบใดที่เรายินดีที่จะทำซ้ำกระบวนการหลายครั้งและยอมรับว่ามันอาจล้มเหลวด้วยความน่าจะเป็นบางอย่าง ซึ่งเราสามารถทำให้น้อยมากได้โดยการรันวงจรให้มากพอ ความคิดสำคัญคือแต่ละครั้งที่รันวงจรให้หลักฐานทางสถิติเกี่ยวกับ $s$ แก่เรา และเราสามารถใช้หลักฐานนั้นเพื่อหาค่า $s$ ด้วยความน่าจะเป็นสูงมากถ้าเรารันวงจรให้มากพอ

สมมติว่าเรารันวงจรอิสระ $k$ ครั้ง สำหรับ $k = n + 10$ ไม่มีอะไรพิเศษเกี่ยวกับจำนวนการวนซ้ำนี้ — เราอาจเลือก $k$ ให้มากขึ้น (หรือน้อยลง) ขึ้นอยู่กับความน่าจะเป็นของความล้มเหลวที่เรายอมรับได้ ดังที่เราจะเห็น การเลือก $k = n + 10$ จะทำให้มั่นใจได้ว่าเรามีโอกาสมากกว่า $99.9$% ในการกู้คืน $s$

โดยการรันวงจร $k$ ครั้ง เราได้สตริง $y^1,...,y^{k} \in \Sigma^n$ ชัดเจนว่า superscript ที่นี่เป็นส่วนหนึ่งของชื่อของสตริงเหล่านี้ ไม่ใช่เลขชี้กำลังหรือดัชนีของบิต ดังนั้นเรามี

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

ตอนนี้เราสร้างเมทริกซ์ $M$ ที่มี $k$ แถวและ $n$ คอลัมน์โดยนำบิตของสตริงเหล่านี้เป็นสมาชิกค่าไบนารี

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

ตอนนี้เราไม่รู้ว่า $s$ คืออะไร — เป้าหมายของเราคือการหาสตริงนี้ แต่จินตนาการสักครู่ว่าเรารู้สตริง $s$ และเราสร้างเวกเตอร์คอลัมน์ $v$ จากบิตของสตริง $s = s_{n-1} \cdots s_0$ ดังนี้

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

ถ้าเราทำการคูณเวกเตอร์เมทริกซ์ $M v$ แบบโมดูลัส $2$ — หมายความว่าเราทำการคูณตามปกติแล้วนำเศษของสมาชิกของผลลัพธ์หลังหารด้วย $2$ — เราจะได้เวกเตอร์ที่มีแต่ศูนย์

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

กล่าวคือ เมื่อถือเป็นเวกเตอร์คอลัมน์ $v$ ตามที่อธิบายไว้ สตริง $s$ จะเป็นสมาชิกของ null space ของเมทริกซ์ $M$ เสมอ ตราบใดที่เราทำเลขคณิตแบบโมดูลัส $2$ สิ่งนี้เป็นจริงทั้งในกรณีที่ $s = 0^n$ และ $s\neq 0^n$ พูดอย่างแม่นยำมากขึ้น เวกเตอร์ที่มีแต่ศูนย์อยู่ใน null space ของ $M$ เสมอ และมีเวกเตอร์ที่มีสมาชิกเป็นบิตของ $s$ ร่วมด้วยในกรณีที่ $s\neq 0^n$

คำถามที่เหลืออยู่คือจะมีเวกเตอร์อื่น ๆ ใน null space ของ $M$ นอกจากเวกเตอร์ที่สอดคล้องกับ $0^n$ และ $s$ หรือไม่ คำตอบคือสิ่งนี้มีโอกาสน้อยลงเรื่อย ๆ เมื่อ $k$ เพิ่มขึ้น — และถ้าเราเลือก $k = n + 10$ null space ของ $M$ จะไม่มีเวกเตอร์อื่นนอกจากที่สอดคล้องกับ $0^n$ และ $s$ ด้วยโอกาสมากกว่า $99.9$% โดยทั่วไป ถ้าเราแทน $k = n + 10$ ด้วย $k = n + r$ สำหรับการเลือกจำนวนเต็มบวก $r$ ใด ๆ ความน่าจะเป็นที่เวกเตอร์ที่สอดคล้องกับ $0^n$ และ $s$ อยู่คนเดียวใน null space ของ $M$ มีค่าอย่างน้อย $1 - 2^{-r}$

โดยใช้พีชคณิตเชิงเส้น เป็นไปได้ที่จะคำนวณคำอธิบายของ null space ของ $M$ แบบโมดูลัส $2$ ได้อย่างมีประสิทธิภาพ โดยเฉพาะ สามารถทำได้โดยใช้ Gaussian elimination ซึ่งทำงานในลักษณะเดียวกันเมื่อทำเลขคณิตแบบโมดูลัส $2$ เหมือนกับเมื่อใช้จำนวนจริงหรือจำนวนเชิงซ้อน ตราบใดที่เวกเตอร์ที่สอดคล้องกับ $0^n$ และ $s$ อยู่คนเดียวใน null space ของ $M$ ซึ่งเกิดขึ้นด้วยความน่าจะเป็นสูง เราสามารถหาค่า $s$ จากผลของการคำนวณนี้

ความยากของคลาสสิก

อัลกอริทึม query คลาสสิก ต้องการ query กี่ครั้งเพื่อแก้ปัญหาของ Simon? คำตอบคือ: มาก โดยทั่วไป

มีข้อความที่แม่นยำที่แตกต่างกันที่สามารถกล่าวเกี่ยวกับความยากของคลาสสิกของปัญหานี้ และนี่คือหนึ่งในนั้น ถ้าเรามีอัลกอริทึม query แบบ probabilistic ใด ๆ และอัลกอริทึมนั้นทำ query น้อยกว่า $2^{n/2 - 1} - 1$ ครั้ง ซึ่งเป็นจำนวน query ที่เป็น exponential ใน $n$ ดังนั้นอัลกอริทึมนั้นจะล้มเหลวในการแก้ปัญหาของ Simon ด้วยความน่าจะเป็นอย่างน้อย $1/2$

บางครั้ง การพิสูจน์ผลลัพธ์ด้านความเป็นไปไม่ได้เช่นนี้อาจเป็นเรื่องที่ท้าทายมาก แต่อันนี้ไม่ยากเกินไปที่จะพิสูจน์ผ่านการวิเคราะห์ความน่าจะเป็นเบื้องต้น อย่างไรก็ตาม ที่นี่เราจะตรวจสอบแค่สัญชาตญาณพื้นฐานเท่านั้น

เรากำลังพยายามหาสตริงที่ซ่อนอยู่ $s$ แต่ตราบใดที่เราไม่ทำ query ฟังก์ชันบนสองสตริงที่มีค่าเอาต์พุตเดิม เราจะได้ข้อมูลเกี่ยวกับ $s$ น้อยมาก พูดอย่างสัญชาตญาณ สิ่งที่เราจะเรียนรู้คือสตริงที่ซ่อนอยู่ $s$ ไม่ใช่ exclusive-OR ของสองสตริงที่แตกต่างกันที่เราทำ query และถ้าเราทำ query น้อยกว่า $2^{n/2 - 1} - 1$ สตริง ยังคงมีทางเลือกมากมายสำหรับ $s$ ที่เรายังไม่ได้ตัดออก เพราะไม่มีคู่สตริงเพียงพอสำหรับทำสิ่งนี้ นี่ไม่ใช่การพิสูจน์อย่างเป็นทางการ มันแค่เป็นความคิดพื้นฐาน

ดังนั้น โดยสรุป อัลกอริทึมของ Simon ให้ข้อได้เปรียบที่โดดเด่นของควอนตัมเหนืออัลกอริทึมคลาสสิกภายในโมเดล query โดยเฉพาะอย่างยิ่ง อัลกอริทึมของ Simon แก้ปัญหาของ Simon ด้วยจำนวน query ที่เป็น linear ในจำนวนบิตอินพุต $n$ ของฟังก์ชันเรา ในขณะที่อัลกอริทึมคลาสสิกใด ๆ แม้แต่ probabilistic ต้องทำ query จำนวนที่เป็น exponential ใน $n$ เพื่อแก้ปัญหาของ Simon ด้วยความน่าจะเป็นของความสำเร็จที่เหมาะสม