نمایش مبدأ برای الگوریتم دویچ

'''الگوریتم دویچ''' (به [[زبان انگلیسی|انگلیسی]]: Deutsch's Algorithm) اولین الگوریتم کوانتومی است که سریعتر از یک الگوریتم کلاسیک کار می‌کند. دیوید دویچ در سال ۱۹۸۵ این الگوریتم را پیشنهاد داد. این الگوریتم کاربردی در دنیای واقعی ندارد ولی اولین مثالی بود که نشان داد الگوریتم‌های کوانتومی وجود دارند که سریعتر از الگوریتم‌های کلاسیک هستند.<ref name="The Royal Society 1985 pp. 97–117">{{cite journal | title=Quantum theory, the Church–Turing principle and the universal quantum computer | journal=Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences | publisher=The Royal Society | volume=400 | issue=1818 | date=1985-07-08 | issn=0080-4630 | doi=10.1098/rspa.1985.0070 | pages=97–117}}</ref>
در این مسئله توابعی با یک متغیر بررسی می‌شوند. ورودی و خروجی می‌توانند مقادیر صفر یا یک باشند؛ بنابراین چهار نوع تابع می‌تواند در این الگوریتم تعریف شود:
{{چپ‌چین}}
<math>f\colon\{0,1\}\rightarrow \{0,1\}</math>
* f(0) = 0 & f(1) = 0
* f(0) = 0 & f(1) = 1
* f(0) = 1 & f(1) = 0
* f(0) = 1 & f(1) = 1
{{پایان چپ‌چین}}

توابع اول و چهارم از لیست بالا یک خروجی برای همه ورودی‌ها دارند و [[تابع ثابت]] خوانده می‌شوند. توابع دوم و سوم از لیست بالا تابع متوازن خوانده می‌شوند زیرا خروجی برای نیمی از وردی‌ها صفر و برای نیمی دیگر یک است. سؤالی که در الگوریتم دویچ مطرح می‌شود این است که یک تابع چند بار باید ارزیابی شود تا بفهمیم ثابت است یا متوازن؟

تحلیل کلاسیک به این صورت است که اگر ورودی صفر باشد و خروجی هم صفر باشد نمی‌دانیم تابع به شکل اول یا دوم از لیست بالا است و باید یک ارزیابی دیگر انجام دهیم تا متوجه شویم خروجی برای یک چه عددی است و تابع در نهایت ثابت است یا متوازن. در مورد ورودی یک به همین ترتیب دوبار ارزیابی تابع لازم است. در حالی که در تحلیل کوانتومی با یک بار ارزیابی تابع می‌توانیم تشخیص دهیم که تابع ثابت است یا متوازن.<ref name="Bernhardt 2019">{{cite book | last=Bernhardt | first=C. | title=Quantum Computing for Everyone | publisher=MIT Press | series=The MIT Press | year=2019 | isbn=978-0-262-03925-3 | url=https://books.google.com.au/books?id=SROKDwAAQBAJ&pg=PR7 | access-date=2023-05-12 | page=145-149}}</ref>
دویچ و جوژا در سال ۱۹۹۲ شکل کلی تری از این الگوریتم را پیشنهاد دادند که به نام الگوریتم دویچ-جوژا شناخته می‌شود.

== الگوریتم دویچ-جوژا ==
الگوریتم دویچ-جوژا (به [[زبان انگلیسی|انگلیسی]]: Deutsch–Jozsa algorithm) شکل تعمیم یافته الگوریتم دویچ است که در سال ۱۹۹۲ به وسیله [[دیوید دویچ]] و ریچارد جوژا پیشنهاد شد. در الگوریتم دویچ یک تابع تک متغیره بررسی می‌شد و هدف این بود که ببینیم این [[تابع ثابت]] است یا متوازن. در الگوریتم دویچ-جوژا با توابع n متغیره سروکار داریم که ورودی و خروجی‌های ان مقادیر صفر و یک است.
{{چپ‌چین}}
<math>f\colon\{0,1\}^n\rightarrow \{0,1\}</math>
{{پایان چپ‌چین}}
در تحلیل کلاسیک برای <math>n</math> متغیر <math>2^n</math>  ورودی وجود دارد. در بهترین حالت می‌توان نوع تابع (ثابت یا متوازن) را با دو پرسش به دست آورد (در حالتی که خروجی‌ها برابر نباشند تابع قطعاً ثابت نخواهد بود) و در بدترین حالت نیاز به مطرح کردن <math>2^{n-1} + 1</math> سؤال خواهیم داشت یعنی تعداد سؤال‌ها با افزایش ورودی‌ها به صورت نمایی افزایش می‌یابد. در حالی که در تحلیل کوانتومی با یک سؤال می‌توانیم دریابیم که تابع ثابت است یا متوازن.<ref name="Bernhardt 2019">{{cite book | last=Bernhardt | first=C. | title=Quantum Computing for Everyone | publisher=MIT Press | series=The MIT Press | year=2019 | isbn=978-0-262-03925-3 | url=https://books.google.com.au/books?id=SROKDwAAQBAJ&pg=PR7 | access-date=2023-05-12 | page=152-157}}</ref>
== جستارهای وابسته ==
* [[الگوریتم کوانتومی]]
* [[اطلاعات کوانتومی]]
* [[نظریه پیچیدگی کوانتومی]]
* [[دیوید دویچ]]

== منابع ==
{{پانویس|چپ‌چین = بله}}

{{ریاضی-خرد}}

[[رده:الگوریتم‌های کوانتومی]]
[[رده:علوم اطلاعات کوانتومی]]