Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Full text

Pdf (167 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 10B table of contents

Pages: 653 - 658

Year of Publication: 2002

ISBN:1-58113-495-9

Author

Sean Hallgren

Caltech, MC, Pasadena, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 29, Citation Count: 14

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.510001 What is a DOI?

ABSTRACT

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
	2	Proceedings of the 4th International Symposium on Algorithmic Number Theory, July 2000
	3	J. Buchmann. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In Séminaire de théorie des nombres, pages 28--41. Paris, 1989.
	4	J. Buchmann and H. C. Williams. Some remarks concerning the complexity of computing class groups of quadratic fields. Journal of Complexity, 7(3):311--315, 1991.
	5	Johannes A. Buchmann , Hugh C. Williams, A key exchange system based on real quadratic fields, Proceedings on Advances in cryptology, p.335-343, July 1989, Santa Barbara, California, United States
	6	Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
	7	M. Ettinger, P. Høyer, and E. Knill. Hidden subgroup states are almost orthogonal. Technical report, quant-ph/9901034, 1999.
	8	Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
	9	Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
	10	Gábor Ivanyos , Frédéric Magniez , Miklos Santha, Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.263-270, July 2001, Crete Island, Greece [doi>10.1145/378580.378679]
	11	H. W. Lenstra, Jr. On the computation of regulators and class numbers of quadratic fields. Lond. (MATH). Soc. Lect. Note Ser., 56:123--150, 1982.
	12	H. W. Lenstra, Jr. Solving Pell's equation. Clay (MATH)ematics Institute Introductory Workshop in Algorithmic Number Theory, MSRI, http://www.msri.org/publications/video/index01.html, August 14-23, 2000.
	13	H. W. Lenstra, Jr. Solving the Pell equation. Notices Amer. (MATH). Soc., 49(2):182--192, Feb. 2002.
	14	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	15	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	16	Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
	17	W. van Dam, S. Hallgren, and L. Ip. Quantum algorithms for some hidden coset problems. Manuscript.
	18	Ulrich Vollmer, Asymptotically Fast Discrete Logarithms in Quadratic Number Fields, Proceedings of the 4th International Symposium on Algorithmic Number Theory, p.581-594, July 02-07, 2000

CITED BY 14

	Wim van Dam , Sean Hallgren , Lawrence Ip, Quantum algorithms for some hidden shift problems, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Dorit Aharonov , Amnon Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Peter W. Shor, Why haven't more quantum algorithms been found?, Journal of the ACM (JACM), v.50 n.1, p.87-90, January 2003
	Arthur Schmidt , Ulrich Vollmer, Polynomial time quantum algorithm for the computation of the unit group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Sean Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Holger Spakowski , Mayur Thakur , Rahul Tripathi, Quantum and classical complexity classes: separations, collapses, and closure properties, Information and Computation, v.200 n.1, p.1-34, 1 July 2005
	Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Oleg Izmerly , Tal Mor, Chosen ciphertext attacks on lattice-based public key encryption and modern (non-quantum) cryptography in a quantum environment, Theoretical Computer Science, v.367 n.3, p.308-323, December, 2006
	Sean Hallgren , Cristopher Moore , Martin Rötteler , Alexander Russell , Pranab Sen, Limitations of quantum coset states for graph isomorphism, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Dorit Aharonov , Vaughan Jones , Zeph Landau, A polynomial quantum algorithm for approximating the Jones polynomial, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Cristopher Moore , Alexander Russell , Piotr Sniady, On the impossibility of a quantum sieve algorithm for graph isomorphism, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Tzvetan S. Metodi , Darshan D. Thaker , Andrew W. Cross, A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.305-318, November 12-16, 2005, Barcelona, Spain
	Peter W. Shor, Progress in Quantum Algorithms, Quantum Information Processing, v.3 n.1-5, p.5-13, October 2004
	Dave Bacon , Debbie Leung, Toward a world with quantum computers, Communications of the ACM, v.50 n.9, September 2007