An efficient quantum circuit for addition in GF(p) and Shor's algorithm

摘要

We decrease the number of qubits in Proos et al.'s quantum circuit for Shor's discrete logarithm algorithm for elliptic curves over the prime field GF(p). To decrease the number of qubits, we use the quantum circuit for addition with no ancillary qubits we have proposed. When we use the circuit for addition in place of the one in Proos et al.'s circuit, the number of qubits decreases from about 5n to 4n without increasing the depth and size, where n is the length of the binary representation for p. Moreover,we construct an efficient quantum circuit for addition in GF(p) that is useful for further decreasing the number of qubits.