An Introduction to Quantum Computing Algorithms

در سال 1994 پیتر شور [65] یک الگوریتم فاکتورسازی برای یک کامپیوتر کوانتومی منتشر کرد که فاکتورهای اول یک عدد صحیح مرکب N را کارآمدتر از الگوریتم های شناخته شده برای یک کامپیوتر کلاسیک می یابد. از آنجایی که دشواری مسئله فاکتورسازی برای امنیت یک سیستم رمزگذاری کلید عمومی بسیار مهم است، علاقه (و تامین مالی) در محاسبات کوانتومی و محاسبات کوانتومی ناگهان شکوفا شد. محاسبات کوان توم رسیده بود. به نظر می رسد مطالعه نقش مکانیک کوانتومی در نظریه محاسبات در اوایل دهه 1980 با انتشارات پل بنیوف [6]' [7] که یک مدل مکانیکی کوانتومی از کامپیوترها و فرآیند محاسبات را در نظر گرفت، آغاز شده است. یک سوال مرتبط اندکی پس از آن توسط ریچارد فاینمن [35] مورد بحث قرار گرفت که از دیدگاهی متفاوت با پرسیدن اینکه چه نوع کامپیوتری باید برای شبیه سازی فیزیک استفاده شود، شروع کرد. تجزیه و تحلیل او او را به این باور رساند که با یک کلاس مناسب از "ماشین های کوانتومی" می توان از هر سیستم کوانتومی تقلید کرد.

In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.