On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine
Summary :
There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.5 pp.579-583
- Publication Date
- 1996/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takashi MIHARA, "On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 5, pp. 579-583, May 1996, doi: .
Abstract: There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_5_579/_p
Copy
@ARTICLE{e79-d_5_579,
author={Takashi MIHARA, },
journal={IEICE TRANSACTIONS on Information},
title={On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine},
year={1996},
volume={E79-D},
number={5},
pages={579-583},
abstract={There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - On the Complexity of Finding Cycles in Periodic Functions Using the Quantum Turing Machine
T2 - IEICE TRANSACTIONS on Information
SP - 579
EP - 583
AU - Takashi MIHARA
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1996
AB - There are some results indicating that a quantum computer seems to be more powerful than ordinary computers. In fact, P.W. Shor showed that a quantum computer can find discrete logarithms and factor integers in polynomial time with bounded error probability. No polynomial time algorithms to find them using ordinary computers are known. In this paper, we show that the cycles in some kinds of periodic functions, e.g., functions proposed as pseudo-random generators, can be found in polynomial time with bounded error probability on a quantum Turing machine. In general, it is known that ordinary computers take exponential time to find the cycles in periodic functions.
ER -
English
