Computational complexity in high-dimensional quantum computing
Tóm tắt
We study an efficiency for operating a full adder/half adder by quantum-gated computing. Fortunately, we have two typical arithmetic calculations discussed in Nakamura and Nagata (Int J Theor Phys 60:70, 2021). The two typical arithmetic calculations are (1 + 1) and (2 + 3). We demonstrate some evaluations of three two-variable functions which are elements of a boolean algebra composed of the four-atom set utilizing the d-dimensional Bernstein–Vazirani algorithm. This is faster than that of its classical apparatus which would require d12 steps. Using the three two-variable functions evaluated here, we demonstrate a typical arithmetic calculation (2 + 3) in the binary system using the full adder operation. The typical arithmetic calculation is faster than that of its classical apparatus which would require d12 steps when we introduce the full adder operation. Another typical arithmetic calculation (1 + 1) is faster than that of its classical apparatus which would require d8 steps when we introduce only the half adder operation. The concrete and specific calculation (2n + 1),(n > 1) is faster than that of a classical apparatus which would require n × d12 steps. The quantum advantage increases when two numbers we treat become very large.
Tài liệu tham khảo
Bernstein E, Vazirani U (1993) Quantum complexity theory. In: Proceedings of 25th annual ACM symposium on theory of computing (STOC ’93), p 11. https://doi.org/10.1145/167088.167097
Bernstein E, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26:1411. https://doi.org/10.1137/S0097539796300921
Cleve R, Ekert A, Macchiavello C, Mosca M (1998) Quantum algorithms revisited. Proc R Soc Lond A 454:339. https://doi.org/10.1098/rspa.1998.0164https://doi.org/10.1098/rspa.1998.0164
Deutsch D (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. Proc R Soc Lond A 400:97. https://doi.org/10.1098/rspa.1985.0070
Deutsch D, Jozsa R (1992) Rapid solution of problems by quantum computation. Proc R Soc Lond A 439:553. https://doi.org/10.1098/rspa.1992.0167https://doi.org/10.1098/rspa.1992.0167
Fujikawa K, Oh CH, Umetsu K (2019) A classical limit of Grover’s algorithm induced by dephasing: Coherence versus entanglement. Modern Physics Letters A, Vol. 34, No. 07n08 1950146. https://doi.org/10.1142/S0217732319501463
Gidney C (2018) Halving the cost of quantum addition. Quantum 2:74. https://doi.org/10.22331/q-2018-06-18-74
Gilbert WJ, Nicholson WK (2004) Modern algebra with applications (Inc Second edition). Wiley, New York
Grover LK (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of 28th Annual ACM Symposium on Theory of Computing, p 212. https://doi.org/10.1145/237814.237866
Li H-S, Fan P, Xia H, Long G-L (2022) The circuit design and optimization of quantum multiplier and divider. Sci China Phys Mech Astron 65:260311. https://doi.org/10.1007/s11433-021-1874-2
Li H-S, Fan P, Xia H, Peng H, Long G-L (2020) Efficient quantum arithmetic operation circuits for quantum image processing. Sci China Phys Mech Astron 63:280311. https://doi.org/10.1007/s11433-020-1582-8https://doi.org/10.1007/s11433-020-1582-8
Liu XS, Long GL, Tong DM, Li F (2002) General scheme for superdense coding between multiparties. Phys Rev A 65:022304. https://doi.org/10.1103/PhysRevA.65.022304
Mehendale DP, Joag PS (2017) A simple algorithm for complete factorization of an N-Partite pure quantum state. Quantum Phys Lett 6(1):73. https://doi.org/10.18576/qpl/060110
Mermin ND (2022) Deconstructing dense coding. Phys Rev A 66:032308. https://doi.org/10.1103/PhysRevA.66.032308
Nagata K, Geurdes H, Patro SK, Heidari S, Farouk A, Nakamura T (2020) Generalization of the Bernstein-Vazirani algorithm beyond qubit systems. Quantum Stud Math Found 7:17. https://doi.org/10.1007/s40509-019-00196-4https://doi.org/10.1007/s40509-019-00196-4
Nagata K, Nakamura T (2020) Some theoretically organized algorithm for quantum computers. Int J Theor Phys 59:611. https://doi.org/10.1007/s10773-019-04354-7https://doi.org/10.1007/s10773-019-04354-7
Nagata K, Nakamura T (2021) A quantum algorithm for a FULL adder operation based on registers of the CPU in a quantum-gated computer. Int J Theor Phys 60:2986. https://doi.org/10.1007/s10773-021-04894-xhttps://doi.org/10.1007/s10773-021-04894-x
Nakamura T, Nagata K (2021) Physics’ evolution toward computing. Int J Theor Phys 60:70. https://doi.org/10.1007/s10773-020-04661-4https://doi.org/10.1007/s10773-020-04661-4
Rennie R (ed) (2015) Oxford dictionary of physics, Seventh ed. Oxford University Press, Oxford
Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of 35th IEEE Annual symposium on foundations of computer science, p. 124. https://doi.org/10.1109/SFCS.1994.365700
Simon DR (1994) On the power of quantum computation. In: Proceedings of 35th IEEE annual symposium on foundations of computer science, p 116. https://doi.org/10.1109/SFCS.1994.365701
Yan F, Gao T (2022) Perfect NOT and conjugate transformations. AAPPS Bull 32:7. https://doi.org/10.1007/s43673-022-00038-3
Yin A, He K, Fan P (2019) Quantum dialogue protocol based on Grover’s search algorithms. Modern Physics Letters A, Vol. 34. No. 21, 1950169. https://doi.org/10.1142/S0217732319501694