Efficient quantum circuits for arithmetic operations and their applications 算術演算のための効率的な量子回路とその応用

この論文をさがす

著者

    • 高橋, 康博 タカハシ, ヤスヒロ

書誌事項

タイトル

Efficient quantum circuits for arithmetic operations and their applications

タイトル別名

算術演算のための効率的な量子回路とその応用

著者名

高橋, 康博

著者別名

タカハシ, ヤスヒロ

学位授与大学

電気通信大学

取得学位

博士 (工学)

学位授与番号

甲第467号

学位授与年月日

2008-03-24

注記・抄録

博士論文

This thesis focuses on constructing efficient quantum circuits for arithmetic operationsand applying them to Shor’s factoring algorithm to answer the question: Whatwould be sufficient computational resources for a quantum computer to be able toperform Shor’s factoring algorithm for a large input number? The answers to theproblem would contribute to our understanding of the computational power of smallquantum circuits such as logarithmic-depth quantum circuits. Moreover, the answerswould be useful for analyzing the detailed relationships between the computationalpower of a quantum computer and the security of cryptosystems and for designinga new cryptosystem that is secure against a quantum computer. First, I constructa linear-size quantum circuit for addition with no ancillary qubits. This is an affirmativeanswer to Cuccaro et al.’s question. Then, using the circuit, I construct alogarithmic-depth quantum circuit for addition with few qubits and apply it to constructingan O(n2 log n)-depth O(n3 log n)-size quantum circuit for Shor’s algorithmwith 2n+O(n/ log n) qubits, where n is the length of the number to be factored. Thenumber of qubits is less than that in any other O(n2 log n)-depth quantum circuit everconstructed for Shor’s algorithm. Then, I construct a quantum circuit for comparisonwith uninitialized ancillary qubits and apply it to constructing an O(n3)-depthO(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+2 qubits. The numberof qubits is less than that in any other quantum circuit ever constructed for Shor’salgorithm. Lastly, on a linear nearest neighbor architecture, I construct a small-sizequantum circuit for the quantum Fourier transform and apply it to constructing anO(n3)-depth O(n3 log n)-size quantum circuit for Shor’s algorithm with 2n+4 qubits.The size is less than that of any other quantum circuit ever constructed for Shor’salgorithm on a linear nearest neighbor architecture.

2007

1アクセス

各種コード

  • NII論文ID(NAID)
    500000435538
  • NII著者ID(NRID)
    • 8000000436841
  • 本文言語コード
    • eng
  • NDL書誌ID
    • 000009368615
  • データ提供元
    • 機関リポジトリ
    • NDL ONLINE
ページトップへ