| |
 |
|
|
Science Forum Index » Physics - Research Forum » Is there a survey on the wide range of algorithms...
Page 1 of 1
|
| Author |
Message |
| Benjamin Gittins... |
 Posted: Fri Jun 13, 2008 9:10 am |
|
|
|
Guest
|
Hi.,
I am looking for a survey on the performance of different
implementations of Shor's algorithms for factoring, finding discrete
logarithms and related algorithms derived from this work. I have
searched for a while without success. I am hoping someone can point
me to such a paper or might be able to provide some assistance.
Specifically I'm looking for information like this:
* Author, Paper Name
* Algorithm Name found in paper
* One line description of what it does (Factoring large numbers, break
RSA, ECDLP, etc)
* Number of operations
* Number of qubits
* Computational model (Adiabatic, standard gate model, etc)
* Degree of parallelism
* Any special limitations on what forms of the problem can't be solved
using this technique
As further background to my request I have found this type of
information is often difficult to extract from a publication. For
example, in the paper by Peter W. Shor, =93Polynomial-Time Algorithms
for Prime Factorization and Discrete Logarithms on a Quantum
Computer=94, http://www.arxiv.org/abs/quant-ph/9508027, the number of
qubits is unfortunately not stated clearly next to the number of
operations for the factoring algorithm. Furthermore there is no direct
statement of qubits and operations for the discrete log algorithm. I
have been kindly informed by the author that I should look at the
careful analysis by Beckman and colleagues listed below to find the
answers.
As it may be useful to others looking for similar information I have
included a short and incomplete list of papers that appear to have
important results in this area:
Peter W. Shor, =93Polynomial-Time Algorithms for Prime Factorization and
Discrete Logarithms on a Quantum Computer=94, http://www.arxiv.org/abs/quant=
-ph/9508027
Beckman, Chari, Devabhaktuni and Preskill, in "Efficient networks for
quantum factoring." http://arxiv.org/abs/quant-ph/9602016
Michele Mosca and Artur Ekert, "The hidden subgroup problem and
eigenvalue estimation on a quantum computer". Lecture Notes in
Computer Science, 1509:174?188, Springer, Berlin, 1999.
http://arxiv.org/abs/quant-ph/9903071
S. Parker, =A0M. B. Plenio, "Efficient factorization with a single pure
qubit", Technical report, =A0quant-ph/0001066, 2000. http://arxiv.org/abs/qu=
ant-ph/0001066
C. Zalka, "Fast versions of Shor's quantum factoring algorithm",
Technical report, quant-ph/9806084, 1998. http://arxiv.org/abs/quant-ph/9806=
084
Jean-Pierre Seifert, "Using fewer Qubits in Shor's Factorization
Algorithm via Simultaneous Diophantine Approximation", Cryptology
ePrint Archive: Report 2000/036, http://eprint.iacr.org/2000/036
D. Boneh and R. Lipton. "Quantum Cryptanalysis of Hidden Linear
Functions" Advances in Cryptology - CRYPTO =9295, pp. 424=96437, 1995.
Michele Mosca and Artur Ekert. "The hidden subgroup problem and
eigenvalue estimation on a quantum computer". Lecture Notes in
Computer Science, 1509:174=96188, Springer, Berlin, 1999.
http://arxiv.org/abs/quant-ph/9903071
John Proos and Christof Zalka, "Shor=92s discrete logarithm quantum
algorithm for elliptic curves", Quantum Information and Computation, 3
(2003), pp. 317-344. http://citeseer.ist.psu.edu/proos03shors.html
Kevin K. H. Cheung, Michele Mosca, "Decomposing Finite Abelian
Groups", (2008), http://arxiv.org/pdf/cs/0101004
Michael Stephen Brown, "Classical Cryptosystems In A Quantum Setting",
http://www.iqc.ca/publications/theses/mbrown.pdf
Cheers,
Benjamin Gittins |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Sun Nov 23, 2008 1:56 pm
|
|