Classical computing, quantum computing, and Shor's factoring algorithm

Details Classical computing, quantum computing, and Shor's factoring algorithm Classical computing, quantum computing, and Shor's factoring algorithm

1999-03-02

arxiv.org/abs/quant-ph/9903008v1

Physics

Quantum Physics

27 pp., no figures, amstex

Scientific paper

This is an expository talk written for the Bourbaki Seminar. After a brief introduction, Section 1 discusses in the categorical language the structure of the classical deterministic computations. Basic notions of complexity icluding the P/NP problem are reviewed. Section 2 introduces the notion of quantum parallelism and explains the main issues of quantum computing. Section 3 is devoted to four quantum subroutines: initialization, quantum computing of classical Boolean functions, quantum Fourier transform, and Grover's search algorithm. The central Section 4 explains Shor's factoring algorithm. Section 5 relates Kolmogorov's complexity to the spectral properties of computable function. Appendix contributes to the prehistory of quantum computing.

Affiliated with

Also associated with

No associations

Rating

Classical computing, quantum computing, and Shor's factoring algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical computing, quantum computing, and Shor's factoring algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical computing, quantum computing, and Shor's factoring algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-290820