Bulletin of the European Association for Theoretical Computer Science

Quantum Computing and the Hunt for Hidden Symmetry.

Gorjan Alagic, Alexander C. Russell

Published Jan 1, 2007• 1 citation

Abstract

In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. 1

Related papers

Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem

JozsaRichard

IEEE MultimediaMar 1, 19960 citations

Quantum factoring, discrete logarithms, and the hidden subgroup problem

Richard Jozsa

Among the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorization and the evaluation of discrete logarithms. This article reviews the essential ingredients of these algorithms and draws out the unifying generalization of the so-called hidden subgroup problem.

arXiv:quant-ph/0012084Computing in Science & EngineeringJan 1, 2001121 citations

Quantum Computing

Oscar Humberto Montiel Ross, Roberto Sepulveda

In the twenty-fi rst century, many signifi cant developments in science and engineering have been achieved through interdisciplinary research. Quantum computing (QC) is about computing with quantum systems, called quantum computers. A quantum computer is a computational device that makes use of the quantum mechanics (QM) phenomena such as entanglement, superposition and interference to perform operations on data. Quantum computers are different from classical binary digital computers since they work with quantum bits. The theoretical model is the quantum turing machine (QTM) which is a normal turing machine (TM) with quantum parallelism. Richard Feynman introduced this fi eld for the fi rst time in the 80’s (Feynman 1982) since he observed that certain quantum-mechanical effects cannot be simulated in an effi cient way using a classical computer. Such observation let to speculate that using quantum effects may become more effi cient computing. The interest grew up in 1994 when Peter Shor published the paper entitled “Algorithms for Quantum Computation : Discrete Logarithms and Factoring” (Shor 1994) where he described polynomial time quantum algorithms for fi nding discrete logarithms and factoring integers.

CRC Press eBooksJan 9, 20140 citations

An Exposition on Peter Shor's Polynomial-Time Factoring Algorithm and Its Effects on Post-Quantum Cryptography

Kristopher Lonnie Watkins

When building cryptosystems, cryptographers focus on finding problems that are not believed to be solvable in polynomial-time. Some of the most popular problems they have found are the Discrete Logarithm Problem and Integer Factoring. The former is used in Diffie-Hellman Key Exachange (DHK) and El Gamal encryption, while the latter is used in RSA. El Gamal and DHK are both very popular, but RSA is more prevalent due to its efficiency.\n Nevertheless, it is plausible that in the next few decades, all three of these systems will likely be useless due to the advances made by Peter Shor in quantum computing. This paper will explain the details of how Shor’s algorithm works and how it accomplishes the above. It will also feature a redesign of the proof of Jeffrey Miller (1975) that efficiently reduces from order finding in a group of order N to factoring N. Hopefully, doing so will aid future students in their studies of quantum algorithms and Post-Quantum Cryptography.

Oct 30, 20190 citations

3 Factorization with Quantum Computers: Shor’s Algorithm

Daniel Neuenschwander

Lecture notes in computer scienceJan 1, 20040 citations

量子計算と量子アルゴリズム

Tetsuro Nishino

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Algorithms executed on QTMs are called quantum algorithms. It is well known that Peter Shor designed a polynomial time quantum algorithm for integer factoring in 1994. In this paper, we first illustrate several major methods of designing efficient quantum algorithms with Shor's algorithm as an example. On the other hand, many researchers are studying how to physically implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computations performed on NMR is slightly different from those performed on QTMs. For example, Shor's factoring algorithm cannot be executed on an NMR quantum computer as it is. In this paper, we show how to factor integers in polynomial time by using NMR quantum computers.

Jul 31, 20030 citations