Efficient quantum circuits for arithmetic operations and their applications 算術演算のための効率的な量子回路とその応用
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
Efficient quantum circuits for arithmetic operations and their applications
- タイトル別名
-
算術演算のための効率的な量子回路とその応用
- 著者名
-
高橋, 康博
- 著者別名
-
タカハシ, ヤスヒロ
- 学位授与大学
-
電気通信大学
- 取得学位
-
博士 (工学)
- 学位授与番号
-
甲第467号
- 学位授与年月日
-
2008-03-24
注記・抄録
博士論文
2007
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.