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

博士論文

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.