Top

Published in:

2020 | OriginalPaper | Chapter

Quantum Solution for the 3-SAT Problem Based on IBM Q

Authors : Ying Zhang, Yu-xiang Bian, Qiang Fan, Junxiu Chen

Published in: Cloud Computing, Smart Grid and Innovative Frontiers in Telecommunications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Quantum computing is currently considered to be a new type of computing model that has a subversive impact on the future. Based on its leading information and communication technology advantages, IBM launched IBM Q Experience cloud service platform, and achieved phased research results in the quantum simulator and programming framework. In this paper, we propose a quantum solution for the 3-SAT problem, which includes three steps: constructing the initial state, computing the unitary \(U_f\) implementing the black-box function f and performing the inversion about the average. In addition, the corresponding experimental verification for an instance of the Exactly-1 3-SAT problem with QISKit, which can connect to IBM Q remotely, is depicted. The experimental result not only show the feasibility of the quantum solution, but also serve to evaluate the functionality of IBM Q devices.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Quantum Searchable Encryption for Cloud Data Based on Delegating Quantum Computing

next chapter Cloud Grazing Management and Decision System Based on WebGIS

Feynman, R.P.: Simulating physics with computers. Int. J. Theor. Phys. 21, 467–488 (1982). https://doi.org/10.1007/BF02650179MathSciNetCrossRef

Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A (Math. Phys. Sci.) 439(1907), 553–558 (1992)MathSciNetMATH

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999) MathSciNetCrossRef

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of ACM Symposium on the Theory of Computing, pp. 212–219 (1996)

Liu, Z.-H., Chen, H.-W., Xu, J., Liu, W.-J., Li, Z.-Q.: High-dimensional deterministic multiparty quantum secret sharing without unitary operations. Quantum Inf. Process. 11(6), 1785–1795 (2011). https://doi.org/10.1007/s11128-011-0333-zMathSciNetCrossRefMATH

Chen, X.B., Tang, X., Xu, G., Dou, Z., Chen, Y.L., Yang, Y.X.: Cryptanalysis of secret sharing with a single d-level quantum system. Quantum Inf. Process. 17(9), 225 (2018)MathSciNetCrossRef

Huang, W., Su, Q., Liu, B., He, Y.H., Fan, F., Xu, B.J.: Efficient multiparty quantum key agreement with collective detection. Sci. Rep. 7(1), 15264 (2017)CrossRef

Liu, W.J., Xu, Y., Yang, C.N., Gao, P.P., Yu, W.B.: An efficient and secure arbitrary N-party quantum key agreement protocol using bell states. Int. J. Theor. Phys. 57(1), 195–207 (2018). https://doi.org/10.1007/s10773-017-3553-xMathSciNetCrossRefMATH

Liu, W.J., Chen, H.W., Li, Z.Q., Liu, Z.H.: Efficient quantum secure direct communication with authentication. Chin. Phys. Lett. 25(7), 2354–2357 (2008)CrossRef

10.

Liu, W.J., Chen, H.W., Ma, T.H., Li, Z.Q., Liu, Z.H., Hu, W.B.: An efficient deterministic secure quantum communication scheme based on cluster states and identity authentication. Chin. Phys. B 18(10), 4105–4109 (2009)CrossRef

11.

Xu, G., Chen, X.-B., Li, J., Wang, C., Yang, Y.-X., Li, Z.: Network coding for quantum cooperative multicast. Quantum Inf. Process. 14(11), 4297–4322 (2015). https://doi.org/10.1007/s11128-015-1098-6MathSciNetCrossRefMATH

12.

Liu, W., Liu, C., Wang, H., Jia, T.: Quantum private comparison: a review. IETE Tech. Rev. 30(5), 439–445 (2013)CrossRef

13.

Liu, W.J., Liu, C., Liu, Z.H., Liu, J.F., Geng, H.T.: Same initial states attack in Yang et al.’s quantum private comparison protocol and the improvement. Int. J. Theor. Phys. 53(1), 271–276 (2014)CrossRef

14.

Liu, W.J., Liu, C., Chen, H.W., Li, Z.Q., Liu, Z.H.: Cryptanalysis and improvement of quantum private comparison protocol based on bell entangled states. Commun. Theor. Phys. 62(2), 210–214 (2014)MathSciNetCrossRef

15.

Liu, W.-J., Liu, C., Wang, H., Liu, J.-F., Wang, F., Yuan, X.-M.: Secure quantum private comparison of equality based on asymmetric W state. Int. J. Theor. Phys. 53(6), 1804–1813 (2014). https://doi.org/10.1007/s10773-013-1979-3CrossRefMATH

16.

Liu, W.-J., et al.: Multiparty quantum sealed-bid auction using single photons as message carrier. Quantum Inf. Process. 15(2), 869–879 (2015). https://doi.org/10.1007/s11128-015-1202-yMathSciNetCrossRefMATH

17.

Liu, W.J., Wang, F., Ji, S., Qu, Z.G., Wang, X.J.: Attacks and improvement of quantum sealed-bid auction with EPR pairs. Commun. Theor. Phys. 61(6), 686–690 (2014)CrossRef

18.

Liu, W.J., Chen, Z.-F., Liu, C., Zheng, Y.: Improved deterministic N-to-one joint remote preparation of an arbitrary qubit via EPR pairs. Int. J. Theor. Phys. 54(2), 472–483 (2015). https://doi.org/10.1007/s10773-014-2241-3CrossRefMATH

19.

Chen, X.-B., Sun, Y.-R., Xu, G., Jia, H.-Y., Qu, Z., Yang, Y.-X.: Controlled bidirectional remote preparation of three-qubit state. Quantum Inf. Process. 16(10), 1–29 (2017). https://doi.org/10.1007/s11128-017-1690-zCrossRefMATH

20.

Qu, Z.G., Wu, S.Y., Wang, M.M., Sun, L., Wang, X.J.: Effect of quantum noise on deterministic remote state preparation of an arbitrary two-particle state via various quantum entangled channels. Quantum Inf. Process. 16(306), 1–25 (2017)MathSciNetMATH

21.

Wang, M.M., Yang, C., Mousoli, R.: Controlled cyclic remote state preparation of arbitrary qubit states. CMC-Comput. Mater. Continua 55(2), 321–329 (2018)

22.

Qu, Z., Cheng, Z., Liu, W., Wang, X.: A novel quantum image steganography algorithm based on exploiting modification direction. Multimedia Tools Appl. 78(7), 7981–8001 (2018). https://doi.org/10.1007/s11042-018-6476-5CrossRef

23.

Qu, Z., Chen, S., Ji, S., Ma, S., Wang, X.: Anti-noise bidirectional quantum steganography protocol with large payload. Int. J. Theor. Phys. 57(6), 1903–1927 (2018). https://doi.org/10.1007/s10773-018-3716-4MathSciNetCrossRefMATH

24.

Qu, Z.G., Zhu, T.C., Wang, J.W., Wang, X.J.: A novel quantum stegonagraphy based on brown states. CMC-Comput. Mater. Continua 56(1), 47–59 (2018)

25.

Liu, W.-J., Chen, Z.-Y., Ji, S., Wang, H.-B., Zhang, J.: Multi-party semi-quantum key agreement with delegating quantum computation. Int. J. Theor. Phys. 56(10), 3164–3174 (2017). https://doi.org/10.1007/s10773-017-3484-6MathSciNetCrossRefMATH

26.

Liu, W.J., Chen, Z.Y., Liu, J.S., Su, Z.F., Chi, L.H.: Full-blind delegating private quantum computation. CMC-Comput. Mater. Continua 56(2), 211–223 (2018)

27.

Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. eprint arXiv (2013)

28.

Liu, W.-J., Gao, P.-P., Yu, W.-B., Qu, Z.-G., Yang, C.-N.: Quantum relief algorithm. Quantum Inf. Process. 17(10), 1–15 (2018). https://doi.org/10.1007/s11128-018-2048-xMathSciNetCrossRefMATH

29.

QISKit: Open Source Quantum Information Science Kit. https://qiskit.org/. Accessed 12 Apr 2018

30.

IBM quantum computing platform. https://www.research.ibm.com/ibm-q/. Accessed 11 Apr 2017

31.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, 10 Anniversary edn. Cambridge University Press, Cambridge (2011)MATH

32.

Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W. H. Freeman and Company, New York (1972)

Title: Quantum Solution for the 3-SAT Problem Based on IBM Q
Authors: Ying Zhang
Yu-xiang Bian
Qiang Fan
Junxiu Chen
Publisher: Springer International Publishing
Book: Cloud Computing, Smart Grid and Innovative Frontiers in Telecommunications
Print ISBN: 978-3-030-48512-2

Electronic ISBN: 978-3-030-48513-9

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-48513-9_33

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner