×

Distributed Bernstein-Vazirani algorithm. (English) Zbl 1522.81062

Summary: Distributed quantum computation has been considered an alternative and beneficial application in the noisy intermediate-scale quantum (NISQ) era, which needs fewer qubits and quantum gates. In this paper, we consider the Bernstein-Vazirani (BV) problem that needs to identify the hidden string \(s\in\{0, 1\}^n\) of Boolean function \(f_s(x) = \langle s \cdot x \rangle = \left(\sum_{i = 0}^{n - 1}s_i \cdot x_i\right) \mod 2 : \{0, 1\}^n\to\{0, 1\}\). In the first instance, we subtly generate \(t\) subfunctions \(f_{S_{n_j}}(m_j) = \langle S_{n_j} \cdot m_j \rangle: \{0, 1\}^{n_j}\to\{0, 1\}\) according to \(f_s(x)\), where \(S_{n_j}\in\{0, 1\}^{n_j}\), \(\sum_{j = 0}^{t - 1} n_j = n\), and \(j\in\{0, 1, \dots, t - 1\}\). After that, we propose a distributed Bernstein-Vazirani algorithm (DBVA) with \(2 \leq t \leq n\) computing nodes, which will exactly acquire \(s = S_{n_0} S_{n_1} \cdots S_{n_{t - 1}}\in\{0, 1\}^n\). To be more specific, (1) the query complexity of DBVA is \(\mathcal{O}(1)\) rather than \(\mathcal{O}(n)\); (2) the circuit depth of DBVA is \(2^{\max(n_0, n_1, \dots, n_{t - 1})} + 3\) less than the circuit depth of the BV algorithm \(2^n + 3\); (3) we request neither auxiliary qubits nor further classical queries; (4) we explicate how DBVA decomposes a 6-qubit BV algorithm into two 3-qubit or three 2-qubit BV algorithms on MindQuantum (a quantum software), which validates the correctness and practicable of DBVA. Eventually, by simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithms have the superiority of resisting noise.

MSC:

81P68 Quantum computation
81P45 Quantum information, communication, networks (quantum-theoretic aspects)
68Q12 Quantum algorithms and complexity in the theory of computing
68Q04 Classical models of computation (Turing machines, etc.)
Full Text: DOI

References:

[1] Benioff, P., The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by turing machines. J. Stat. Phys., 5, 563-591 (1980) · Zbl 1382.68066
[2] Benioff, P., Quantum mechanical Hamiltonian models of turing machines. J. Stat. Phys., 3, 515-546 (1982) · Zbl 0514.68055
[3] Deutsch, D., Quantum theory, the church-turing principle and the universal quantum computer. Proc. R. Soc. Lond. Ser. A, 1818, 97-117 (1985) · Zbl 0900.81019
[4] Deutsch, D.; Jozsa, R., Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A, 553-558 (1907) · Zbl 0792.68058
[5] Simon, D. R., On the power of quantum computation. SIAM J. Comput., 1411-1473 (1997)
[6] Shor, P. W., Algorithms for quantum computation: discrete logarithms and factoring, 124-134
[7] Grover, L. K., Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 2, 325 (1997)
[8] Harrow, A. W.; Hassidim, A.; Lloyd, S., Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 15 (2009)
[9] Bernstein, E.; Vazirani, U., Quantum complexity theory, 11-20 · Zbl 1310.68080
[10] Bernstein, E.; Vazirani, U., Quantum complexity theory. SIAM J. Comput., 5, 1411-1473 (1997) · Zbl 0895.68042
[11] Li, H.; Yang, L., A quantum algorithm for approximating the influences of Boolean functions. Quantum Inf. Process., 6, 1787-1797 (2015) · Zbl 1317.81063
[12] Xie, Z.; Qiu, D., Quantum algorithms on walsh transform and hamming distance for boolean functions. Quantum Inf. Process., 6, 139 (2018) · Zbl 1448.81261
[13] Younes, A., A fast quantum algorithm for the affine Boolean function identification. Eur. Phys. J. Plus., 2, 34 (2015)
[14] Nagata, K.; Resconi, G.; Nakamura, T.; Batle and, J., A generalization of the Bernstein-Vazirani algorithm. MOJ Eco. Environ. Sci., 1, 00010-00012 (2017)
[15] Preskill, J., Quantum computing in the NISQ era and beyond. Quantum, 79 (2018)
[16] Cirac, J. I.; Zoller, P., Quantum computations with cold trapped ions. Phys. Rev. Lett., 4091-4094 (1995)
[17] Lu, C. Y.; Zhou, X. Q.; Guhne and, O., Experimental entanglement of six photons in graph states. Nat. Phys., 91-95 (2007)
[18] Makhlin, Y.; Schön, G.; Shnirman, A., Quantum-state engineering with josephson-junction devices. Rev. Modern Phys., 357-400 (2001)
[19] Berezovsky, J.; Mikkelsen, M. H.; Stoltz, N. G., Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 349-352 (2008)
[20] Hanson, R.; Awschalom, D. D., Review article Coherent manipulation of single spins in semiconductors. Nature, 1043-1049 (2008)
[21] Endo, S.; Cai, Z.; Benjamin, S. C.; Yuan, X., Hybrid quantum-classical algorithms and quantum error mitigation. J. Phys. Soc. Japan (2001)
[22] Buhrman, H.; Röhrig, H., Distributed quantum computing, 1-20, series Title: Lecture Notes in Computer Science · Zbl 1124.68361
[23] Yimsiriwattana, A.; Lomonaco, S. J., Distributed quantum computing: A distributed shor algorithm. Quantum Inf. Comput., 360-372 (2004)
[24] Beals, R.; Brierley, S.; Gray and, O., Efficient distributed quantum computing. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 2153 (2013) · Zbl 1371.81074
[25] Li, K.; Qiu, D. W.; Li, L.; Zheng, S.; Rong, Z., Application of distributed semi-quantum computing model in phase estimation. Inform. Process. Let., 23-29 (2017) · Zbl 1401.68082
[26] Avron, J.; Casper, O.; Rozen, I., Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A (2021)
[27] Qiu, D. W.; Luo, L.; Xiao, L. G., Distributed Grover’s algorithm (2022), arXiv:2204.10487v3
[28] Tan, J. W.; Xiao, L. G.; Qiu, D. W.; Luo, L.; Mateus, P., Distributed quantum algorithm for Simon’s problem. Phys. Rev. A (2022)
[29] Xiao, L. G.; Qiu, D. W.; Luo, L., Distributed Shor’s algorithm. Quantum Inf. Comput., 27-44 (2023)
[30] Xiao, L. G.; Qiu, D. W.; Luo, L., Distributed quantum-classical hybrid Shor’s algorithm (2023), arXiv:2304.12100
[31] Zhou, X.; Qiu, D. W.; Luo, L., Distributed exact Grover’s algorithm. Front. Phys., 5, 51305 (2023)
[32] Li, H.; Qiu, D. W.; Luo, L., Distributed exact quantum algorithms for deutsch-jozsa problem (2023), arXiv:2303.10663
[33] Li, H.; Qiu, D. W.; Luo, L.; Mateus, P., Exact distributed quantum algorithm for generalized Simon’s problem (2023), arXiv:2307.14315
[34] MindQuantum (2021), https://gitee.com/mindspore/mindquantum
[35] R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials, in: Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280), 1998, pp. 352-361.
[36] Nielsen, M. A.; Buhrman, H.; Clever and, R., Quantum Computation and Quantum Information (2002), Cambridge University Press: Cambridge University Press Cambridge
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.