Top

Published in:

2019 | OriginalPaper | Chapter

2. Bits and Qubits

Authors : Franklin de Lima Marquezino, Renato Portugal, Carlile Lavor

Published in: A Primer on Quantum Computing

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 an interdisciplinary field of research, and it is natural that many people starting in this area should feel uncomfortable with the fundamentals of either computer science or physics. In this chapter, we briefly review the basic concepts necessary to follow the rest of the book.

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 Introduction

next chapter Grover’s Algorithm for Unstructured Search

Sometimes it may be convenient to have a CNOT with negative control, so that the target bit is flipped if and only if the control bit is zero. A negative control is usually represented in the circuit model by replacing the full bullet • by an empty bullet ∘ on the control line.

Currently, there is an excellent website known as the Quantum Algorithm Zoo, available at http://math.nist.gov/quantum/zoo/.

Other influential models are adiabatic quantum computing [16, 44], topological quantum computing [22, 24, 34] , cluster-state quantum computing (a.k.a. measurement-based quantum computing or one-way quantum computing) [35, 40] , quantum Turing machines [14, 45], quantum random access machines (qRAM) [17, 31] , deterministic quantum computing with one qubit (DQC1) [13, 23] , IQP computing (a.k.a. temporally unstructured quantum computations) [8, 42], quantum walks [10, 11, 27], and the quantum query model [2, 6], for instance.

T gate is also known in the literature as the π∕8 gate, which may seem a little counterintuitive. The reader should consider that as a special case P(2π∕8).

Sometimes it may be convenient to have a CNOT with negative control, so that the target qubit is flipped if and only if the control qubit is \({\left \vert {0}\right \rangle }\). A negative control is usually represented in the circuit model by replacing the full bullet • by an empty bullet ∘ on the control line.

Negative controls can also be applied in this case. The notation is the same as the one adopted in classical and quantum CNOTs, that is, replacing the full bullet • by the empty bullet ∘ on the negative control lines.

Microsoft LIQUiD can be downloaded from http://stationq.github.io/Liquid. The Microsoft Quantum Development Kit, which includes Q#, can be downloaded from https://www.microsoft.com/en-us/quantum/development-kit.

IBM Quantum Experience can be accessed at https://www.research.ibm.com/ibm-q/.

ProjectQ can be downloaded from http://projectq.ch.

More details at https://www.rigetti.com/qcs.

Aaronson, S.: Quantum Computing since Democritus. Cambridge University Press, New York (2013)CrossRef

Ambainis, A.: Quantum query algorithms and lower bounds. In: Löwe, B., Piwinger, B., Räsch, T. (eds.) Classical and New Paradigms of Computation and their Complexity Hierarchies, pp. 15–32. Springer, Amsterdam, (2004)CrossRef

Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007). https://doi.org/10.1137/S0097539705447311 MathSciNetCrossRef

Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, New York (2009)CrossRef

Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995). https://doi.org/10.1103/PhysRevA.52.3457 CrossRef

Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of 18th IEEE Annual Conference on Computational Complexity, 2003, pp. 179–193 (2003). https://doi.org/10.1109/CCC.2003.1214419

Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411–1473 (1997). https://doi.org/10.1137/S0097539796300921 MathSciNetCrossRef

Bremner, M.J., Jozsa, R., Shepherd, D.J.: Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. 467(2126), 459–472 (2011). https://doi.org/10.1098/rspa.2010.0301 MathSciNetCrossRef

Chandra, R., Jacobson, N.T., Moussa, J.E., Frankel, S.H., Kais, S.: Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer. Phys. Rev. A 90, 012,308 (2014). https://doi.org/10.1103/PhysRevA.90.012308 CrossRef

10.

Childs, A.M.: Universal computation by quantum walk. Phys. Rev. Lett. 102, 180,501 (2009). https://doi.org/10.1103/PhysRevLett.102.180501 MathSciNetCrossRef

11.

Childs, A.M., Gosset, D., Webb, Z.: Universal computation by multiparticle quantum walk. Science 339(6121), 791–794 (2013). https://doi.org/10.1126/science.1229957 MathSciNetCrossRef

12.

Cohen-Tannoudji, C., Diu, B., Laloë, F.: Quantum Mechanics. Wiley, Hoboken (1977)MATH

13.

Datta, A., Shaji, A., Caves, C.M.: Quantum discord and the power of one qubit. Phys. Rev. Lett. 100, 050,502 (2008). https://doi.org/10.1103/PhysRevLett.100.050502 CrossRef

14.

Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. A Math. Phys. Eng. Sci. 400(1818), 97–117 (1985). https://doi.org/10.1098/rspa.1985.0070 MathSciNetCrossRef

15.

De Vos, A.: Reversible Computing: Fundamentals, Quantum Computing, and Applications. Wiley, Hoboken (2011)MATH

16.

Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. Technical Report MIT-CTP-2936, Massachusetts Institute of Technology (2000). ArXiv:quant-ph/0001106

17.

Gay, S.J.: Quantum programming languages: survey and bibliography. Math. Struct. Comput. Sci. 16(4), 581–600 (2006). https://doi.org/10.1017/S0960129506005378 MathSciNetCrossRef

18.

Hardy, Y., Steeb, W.H.: Classical and Quantum Computing: With C++ and Java Simulations. Birkhäuser, Basel (2001). https://doi.org/10.1007/978-3-0348-8366-5 CrossRef

19.

Hirvensalo, M.: Quantum computing. In: Natural Computing Series. Springer, Berlin (2001)CrossRef

20.

Hoffman, K., Kunze, R.A.: Linear Algebra. Prentice-Hall, Upper Saddle River (1971)MATH

21.

Kaye, P., Laflamme, R., Mosca, M.: An Introduction to Quantum Computing. Oxford University Press, Oxford (2007)MATH

22.

Kitaev, A.: Fault-tolerant quantum computation by anyons. Ann. Phys. 303(1), 2–30 (2003). https://doi.org/10.1016/S0003-4916(02)00018-0 MathSciNetCrossRef

23.

Knill, E., Laflamme, R.: Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672–5675 (1998). https://doi.org/10.1103/PhysRevLett.81.5672 CrossRef

24.

Lahtinen, V., Pachos, J.K.: A short introduction to topological quantum computation. SciPost Phys. 3, 021 (2017). https://10.21468/SciPostPhys.3.3.021CrossRef

25.

Lang, S.: Linear Algebra. Springer, Heidelberg (1989)

26.

Lewis, H.R., Papadimitriou, C.H.: Elements of the Theory of Computation, 2nd edn. Prentice-Hall, Upper Saddle River (1997)

27.

Lovett, N.B., Cooper, S., Everitt, M., Trevers, M., Kendon, V.: Universal quantum computation using the discrete-time quantum walk. Phys. Rev. A 81, 042,330 (2010). https://doi.org/10.1103/PhysRevA.81.042330 MathSciNetCrossRef

28.

Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pp. 1109–1117. Society for Industrial and Applied Mathematics, Philadelphia (2005)

29.

Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM J. Comput. 40(1), 142–164 (2011). https://doi.org/10.1137/090745854 MathSciNetCrossRef

30.

Messiah, A.: Quantum Mechanics. Dover, Mineola (2014)MATH

31.

Miszczak, J.A.: Models of quantum computation and quantum programming languages. Bull. Acad. Pol. Sci. Tech. Sci. 59(3), 305–324 (2011). https://doi.org/10.2478/v10175-011-0039-5 MATH

32.

Miszczak, J.A.: High-level Structures for Quantum Computing. Synthesis Lectures on Quantum Computing. Morgan & Claypool, San Rafael (2012)

33.

Montanaro, A.: Quantum algorithms: an overview. NPJ Quantum Inf. 2(15023) (2016). https://doi.org/10.1038/npjqi.2015.23

34.

Nayak, C., Simon, S.H., Stern, A., Freedman, M., Das Sarma, S.: Non-abelian anyons and topological quantum computation. Rev. Mod. Phys. 80, 1083–1159 (2008). https://doi.org/10.1103/RevModPhys.80.1083 MathSciNetCrossRef

35.

Nielsen, M.A.: Cluster-state quantum computation. Rep. Math. Phys. 57(1), 147–161 (2006). https://doi.org/10.1016/S0034-4877(06)80014-5 MathSciNetCrossRef

36.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University, Cambridge (2010). https://doi.org/10.1017/CBO9780511976667

37.

Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Pub Co, Boston (1994)MATH

38.

Perumalla, K.S.: Introduction to Reversible Computing. Computational Science Series. Chapman & Hall/CRC, Boca Raton (2013)

39.

Portugal, R.: Quantum Walks and Search Algorithms. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-97813-0 CrossRef

40.

Raussendorf, R., Briegel, H.J.: A one-way quantum computer. Phys. Rev. Lett. 86, 5188–5191 (2001). https://doi.org/10.1103/PhysRevLett.86.5188 CrossRef

41.

Reichardt, B.W.: Reflections for quantum query algorithms. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pp. 560–569. Society for Industrial and Applied Mathematics, Philadelphia (2011)

42.

Shepherd, D., Bremner, M.J.: Temporally unstructured quantum computation. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. (2009). https://doi.org/10.1098/rspa.2008.0443 MathSciNetCrossRef

43.

Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society, Washington (1994). https://doi.org/10.1109/SFCS.1994.365700

44.

van Dam, W., Mosca, M., Vazirani, U.: How powerful is adiabatic quantum computation? In: Proceedings 2001 IEEE International Conference on Cluster Computing, pp. 279–287 (2001). https://doi.org/10.1109/SFCS.2001.959902

45.

Vazirani, U.V.: A survey of quantum complexity theory. In: Lomonaco Jr., S.J. (ed.) Quantum Computation: A Grand Mathematical Challenge for the Twenty-First Century and the Millennium. Proceedings of Symposia in Applied Mathematics, vol. 58, pp. 193–217. American Mathematical Society, Providence (2002)CrossRef

46.

Viamontes, G.F., Markov, I.L., Hayes, J.P.: Quantum Circuit Simulation. Springer, Amsterdam (2009)CrossRef

Title: Bits and Qubits
Authors: Franklin de Lima Marquezino
Renato Portugal
Carlile Lavor
Publisher: Springer International Publishing
Book: A Primer on Quantum Computing
Print ISBN: 978-3-030-19065-1

Electronic ISBN: 978-3-030-19066-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-19066-8_2

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