الگوریتم سایمون

الگوریتم سایمون (به انگلیسی: Simon's algorithm) یک از الگوریتم‌های کوانتومی است که برای حل مسئله سایمون پیشنهاد شد. این الگوریتم در سال ۱۹۹۴ به وسیله دنیل سایمون پیشنهاد شد. سایمون نشان داد که الگوریتم کوانتومی وی می‌تواند مسئله سایمون را به صورت نمایی سریعتر از الگوریتم کلاسیک حل کند. در واقع الگوریتم سایمون می‌تواند مسئله سایمون را با استفاده از تعداد خطی پرسش حل کند در حالی که الگوریتم کلاسیک نیاز به پرسش‌هایی با تعداد نمایی دارد.

فرض کنید تابعی داریم که ورودی آن رشته‌های دودویی به طول $n$ و خروجی آن نیز رشته‌های دودویی به طول $n$ است. این تابع یک ویژگی خاص دارد و ان این است که یک رشته دودویی $s$ وجود دارد به طوری که:

$f(x)=f(y)$ اگر و تنها اگر $x\oplus y\in \{0^{n},s\}$

نماد $\oplus$ در این گزاره به معنای یای انحصاری (XOR) است. به طوری که

• 0 XOR 0 = 0
• 1 XOR 0 = 1
• 0 XOR 1 = 1
• 1 XOR 1 = 0

و در آن $s$ نمی‌تواند رشته‌ای با رقمهای کلا صفر باشد. هدف مسئله سایمون این است که این رشته $s$ را پیدا کنیم.

• $000\oplus 110=110$
• $001\oplus 110=111$
• $010\oplus 110=100$
• $011\oplus 110=101$
• $011\oplus 110=101$
• $101\oplus 110=011$
• $110\oplus 110=000$
• $111\oplus 110=001$

بنابراین

• $f(000)=f(110)=101$
• $f(001)=f(111)=010$
• $f(010)=f(100)=111$
• $f(011)=f(101)=000$

البته ما نه تابع $f$ را می‌دانیم و نه رشته $s$. سؤال این است که تابع $f$ چند بار باید ارزیابی شود تا بتوانیم رشته $s$ را بیابیم؟ در تحلیل کلاسیک در بدترین حالت نیاز به مطرح کردن $2^{n-1}+1$ سؤال خواهیم داشت. در تحلیل کوانتومی برای محاسبه $s$ باید $n-1$ معادلات خطی مستقل را حل کنیم که الگوریتم‌های مشخصی برای انجام آن وجود دارد.

جستارهای وابسته

• الگوریتم کوانتومی
• اطلاعات کوانتومی
• نظریه پیچیدگی کوانتومی