Quantum Resource Counts for Operations Constructed from an Addition Circuit
Shaun Miller · 2020
An adversary armed with a quantum computer has algorithms at their disposal, which are capable of breaking our current methods of encryption. Even with the birth of post-quantum cryptography, some of best cryptanalytic algorithms are still quantum. Lattice reduction algorithms require several arithmetic operations such as addition, multiplication, and division. Resource counts of quantum circuits determine the practicality of simulating an operation on a quantum computer. Each of the previous operations are constructed from a single addition circuit designed by Takahashi et al. and implemented in the open-source software framework for quantum computing, ProjectQ. We also include a novel approach to designing a circuit for dot product which can be used in Gram-Schmidt orthogonalization, an algorithm often found in lattice reduction. Tiepelt and Szenpieniec provide a quantum circuit for the Gram-Schmidt orthogonalization algorithm. We design modifications to their circuit to better suit the implemented arithmetic operation circuits. Resource estimations are then given for small-dimensional cases.