On zeros of exponential polynomials and quantum algorithms

DOI10.1007/S11128-009-0148-3MaRDI QIDQ989909zbMATH OpenOpenAlexFDO

Authors Yoshitaka Sasaki

Publication date 23 August 2010

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.1657

zbMATH Keywords

discrete logarithmquantum computingcharacter sumexponential congruence

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: We calculate the zeros of an exponential polynomial of some variables by a classical algorithm and quantum algorithms which are based on the method of van Dam and Shparlinski, they treated the case of two variables, and compare with the complexity of those cases. Further we consider the ratio (classical/quantum) of the complexity. Then we can observe the ratio is virtually 2 when the number of the variables is sufficiently large.

Recommendations

• scientific article; zbMATH DE number 5320307
• On the Complexity of Polynomial Zeros
• Polynomials, quantum query complexity, and Grothendieck's inequality
• Quantum algorithms and approximating polynomials for composed functions with shared inputs
• Classical and Quantum Algorithms for Exponential Congruences
• Quantum computation of zeta functions of curves
• scientific article; zbMATH DE number 3974292
• Efficient quantum algorithms of finding the roots of a polynomial function
• A note on quantum algorithms and the minimal degree of \(\varepsilon\)-error polynomials for symmetric functions
• STACS 2005

Cites work

• scientific article; zbMATH DE number 3886001 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• Classical and Quantum Algorithms for Exponential Congruences
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Cited in

(5)

• scientific article; zbMATH DE number 5320307 (Why is no real title available?)
• Classical and Quantum Algorithms for Exponential Congruences
• Efficient quantum algorithms of finding the roots of a polynomial function
• Characteristic roots for two-lag linear delay differential equations
• ON FINDING SOLUTIONS TO EXPONENTIAL CONGRUENCES

This page was built for publication: On zeros of exponential polynomials and quantum algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989909)