Institute of Physics eBooks
Computational complexity in quantum computing
Koji Nagata, Do Ngoc Diep, Ahmed Farouk, Tadao Nakamura
Abstract
Our aim is of studying the efficiency of two typical arithmetic calculations {[T. Nakamura and K. Nagata, Int. J. Theor. Phys. {\bf 60}, 70 (2021)]} using the principle of quantum mechanics. We demonstrate some evaluations of three two-variable functions which are elements of a boolean algebra composed of the four-atom set utilizing the Bernstein--Vazirani algorithm. This is faster than a classical apparatus, which would require $2^{12}=4096$ evaluations. Finally, using the three two-variable functions evaluated here, we demonstrate two typical arithmetic calculations in the binary system. Hence, our calculations are faster than a classical apparatus, which would require $2^{12}=4096$ evaluations.