Shor’s Algorithm Using Efficient Approximate Quantum Fourier Transform

Shor’s algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor’s algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform […]

Hardness of Braided Quantum Circuit Optimization in the Surface Code

Large-scale quantum information processing requires the use of quantum error-correcting codes to mitigate the effects of noise in quantum devices. Topological error-correcting codes, such as surface codes, are promising candidates, as they can be implemented using only local interactions in a 2-D array of physical qubits. Procedures, such as defect braiding and lattice surgery, can […]

The Optimization and Application of 3-Bit Hermitian Gates and Multiple Control Toffoli Gates

The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford+T circuits. Compared with the Peres gate, its implementation circuit requires more controlled- not (cnot) gates. However, the Peres gate is not Hermitian. This article reports four 3-bit Hermitian gates named LI gates, whose realized circuits have the same T-count, T-depth, and cnot […]

Fault-Tolerant Resource Estimation of Quantum Random-Access Memories

Quantum random-access lookup of a string of classical bits is a necessary ingredient in several important quantum algorithms. In some cases, the cost of such quantum random-access memory (qRAM) is the limiting factor in the implementation of the algorithm. In this article, we study the cost of fault-tolerantly implementing a qRAM. We construct and analyze […]