Testing shift-equivalence of polynomials using quantum machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing shift-equivalence of polynomials using quantum machines

Full text

Pdf (649 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1996 international symposium on Symbolic and algebraic computation table of contents

Zurich, Switzerland

Pages: 49 - 54

Year of Publication: 1996

ISBN:0-89791-796-0

Author

D. Grigoriev

Department of Computer Science & Department of Mathematics, Penn State University, University Park, PA

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 4, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/236869.236897 What is a DOI?

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, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.11-20, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167097]
	2	T. Beth, Verfahren der schnelIen Fourier-transformation, (Teubner, Stuttgart, 1984)
	3	A. Chistov, D. Grigoriev, Solving algebraic systems in subexponential time. I, II., Preprints LOMI E-9-83, E- 10-83, Leningrad, 1983
	4	D. Coppersmith An approximate Fourier transform useful in quantum factoring Research report 19642, IBM, 1994
	5	Dima Grigoriev , Marek Karpinski, An approximation algorithm for the number of zeros of arbitrary polynomials over GF[q], Proceedings of the 32nd annual symposium on Foundations of computer science, p.662-669, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185433]
	6	Dima Grigoriev , Marek Karpinski, A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.162-169, May 10-14, 1993
	7	Dima Yu. Grigoriev , Y. N. Lakshman, Algorithms for computing sparse shifts for multivariate polynomials, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.96-103, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220359]
	8	R. M. Kapp , M. Luby , N. Madras, Monte-Carlo approximation algorithms for enumeration problems, Journal of Algorithms, v.10 n.3, p.429-448, September 1989 [doi>10.1016/0196-6774(89)90038-2]
	9	M. Karpinski, I. Shparlinski, Efficient approximation algorithms for sparse polynomials over finite fields, Technical Report 94-029, ICSI, Berkeley, 1994
	10	Y. N. Lakshman , B. David Saunders, On computing sparse shifts for univariate polynomials, Proceedings of the international symposium on Symbolic and algebraic computation, p.108-113, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190373]
	11	R. Loos, Generalized polynomial remainder sequences, in B. Buchberger, J. Calmer, R. Loos, eds., Computer Algebra, (Springer, Berlin, 1982)
	12	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	13	P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. FOCS, (IEEE, 1994), 124-134
	14	D. R. Simon, On the power of quantum computation, Proc. FOCS (IEEE, 1994), 116-123
	15	R. Smolensky, Private communication, 1995
	16	A. Yao, Quantum circuit complexity, Proc. FOCS (IEEE, 1993), 352-360
	17	A. Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem, Preprint of the Institute for Theoretical Physics, Moscow, October 1995
	18	Dan Boneh , Richard J. Lipton, Quantum Cryptanalysis of Hidden Linear Functions (Extended Abstract), Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.424-437, August 27-31, 1995