Quantum Computing

From SI410
Jump to: navigation, search
The Sycamore chip is composed of 54 qubits, each made of superconducting loops. [1]

Quantum computing combines computer science with quantum mechanics.[2] More specifically, it can be described as a “vast multifaceted discipline spanning specializations across mathematics, theoretical and applied computer science, condensed matter physics, quantum field theory, communications and information theory and cryptography.”[3] Quantum computers possess exponentially stronger computational power due to the use of quantum bits, or qubits. Compared to traditional bits, qubits possess double the processing power by exploiting the natural phenomenon known as superposition. This method of processing can lead to faults in computer security that are currently indefensible. There are several different types of quantum computers, but the most prevalent today uses a quantum circuit model. The which utilizes the quantum mechanical phenomena known as quantum entanglement for quantum computing. This model uses entangled particles, the qubits, to make computations; the qubits are arranged in an array, which is then called a quantum chip or circuit.[4]

Quantum computing is a developing technology that presents potential threats to any sector that is reliant on processing power or cryptographic security. Other ethical concerns are raised over the possibility of a few select entities having the access and the ability to use quantum processing power, specifically for large data breaches, and how it may impact the protection of personal data over the internet.


Image of IBM's quantum computer Q

Quantum computing was first conceived by American physicist Paul Benioff in his paper[5] published in the Journal of Statistical Physics in 1980 describing a quantum mechanical model of a Turing machine. It was in the 1980s that American theoretical physicist Richard Feynman[6] and later Russian mathematician Yuri Manin suggested that quantum computers could go about completing tasks that regular computers would not be able to[7]. A turning point in the relevance of quantum computing was when Peter Shor conceived of a quantum algorithm with the theoretical capacity to decrypt RSA encrypted communications[8]. Experimental progress in the later 1990s led tech corporations and governments, often working hand in hand, to invest more time and effort into the development of quantum computing, ramping up investment from then to the present day. Along the way, multiple kinds of quantum computers have been considered, the most popular being the quantum circuit, utilizing qubits in interaction with various quantum logic gates. These quantum logic gates are only one of the multiple computing models being developed as means to the ultimate goal of quantum supremacy, others include techniques such as quantum annealing and adiabatic quantum computation.

Quantum Supremacy

Quantum supremacy or quantum advantage is when a complex problem that cannot be feasibly calculated by traditional computers or even more modern supercomputers is then calculated by a well-ordered, highly entangled quantum system. For example, the traveling salesperson problem is a combinatorial optimization problem that considers a salesperson that has a number of cities to visit and needs to figure out the route that takes the shortest amount of time. This sounds easy, but for a classical computer to simulate every possible route would take lifetimes to compute and is therefore considered an unfeasible problem to solve on a traditional computer. However, a quantum computer would solve this problem in minutes because it would consider many routes at the same time. [9]

In 2019, nature, a scholarly scientific journal, published a paper submitted by Google in which they claimed to have reached a key milestone in the history of computing, which is quantum supremacy. Google claimed that their quantum chip, named Sycamore, had solved a problem that they estimate, would take a traditional computer system approximately 10,000 years to solve. The task was to demonstrate quantum supremacy by generating the probability distribution of all the possible outcomes from a quantum random number generator with its 53 qubit array. Simulating this distribution on a classical system is incredibly challenging, however, Google's quantum system solved the problem in approximately three minutes proving that a quantum computer can calculate something that, in practice, is impossible on a traditional computer. [10]

Moore's Law and the Quantum Fix

Classical computing power has been on an exponential increase over the past 50 years. Evidence of this can be seen using Moore’s Law [11], which states that “the number of transistors in an integrated circuit doubles about every two years.” This decrease in transistor size forces quantum mechanical action to be accounted for. Eventually, these transistors will become too small, meaning quantum tunneling[12] could limit the ability for Moore’s Law to continue. To overcome this, quantum computers instead manipulate qubits, rather than their classical counterparts’ use of transistors. Qubits[13] is the quantum equivalent of classical computer’s bits, where everything is represented in two states: ‘1’ and ‘0’, or ‘true’ and ‘false’. Unlike their bit counterparts, qubits are capable of being three states: ‘1’, ‘0’, and ‘both’ (or equivalently, ‘true’, ‘false’, and ‘both’). The resulting difference in computational power can be seen in any tree branching structure, like maze solving. Where a classical computer would have to check a path, return when its algorithm hit a dead end, and repeat until the correct end is reached, a quantum computer can instead check both routes concurrently until the end is reached [14]. Google’s quantum processor, Sycamore, “completed a task in 200 seconds that Google claimed would take state-of-the-art supercomputers 10,000 years to finish” [15]. This computational power has large implications in data security since many cryptographically secure algorithms are based on the fact that their inherent mathematical assumptions are computationally taxing.

Quantum Solvable Cryptography

Simple version of how RSA works [16]

RSA (Rivest–Shamir–Adleman) encryption[17] is a widely-used public-key cryptosystem that relies on the “factoring problem."[18] RSA allows for cryptographically secure communication because, on state-of-the-art classical supercomputers, the work it takes to generate a key from two prime numbers (what the users would do) is exponentially easier than the work it takes to factor the resulting number into its two primes (what an attacker would have to do to break RSA).

Step by Step RSA[19]:

1. Select two large prime numbers: P and Q

2. Calculate N and O where N = P * Q and O is (P - 1)(Q - 1)

3. Select an E where E is relatively prime to O

4. Find D where (E * D) mod O ≡ 1

5. Public Key: (E, N)

    Private Key: (D, N)

6. To encrypt message x: x^E mod N

    To decrypt message x: x^D mod N

With sufficiently high prime numbers, classical computers are currently incapable of breaking RSA encryption in polynomial time, but this is not the case for quantum computers. As a result of quantum computer’s computational power, the factoring problem is no longer sufficiently hard to be cryptographically secure. This lack of security will have large-scale implications as RSA encryption is a cryptographic primitive utilized in a large number of HTTPS websites[20].

Ethical Concerns

International abuse of power and distributional issues

RSA is currently being utilized worldwide to create secure connections to the Internet, sending text messages between mobile phones and email programs, and for signing contracts and official documents digitally.[21] A major push in quantum computing research is the notion that it could potentially crack current public-key cryptography schemes, like RSA encryption.[21] There are cryptographers currently working to build post-quantum secure cryptography, however, there is no countermeasure to quantum computing that has been developed yet. [22] This raises the concern that if one country has access to quantum computing before other countries have it, the post-quantum country will have uninhibited access to a majority of the world’s internet traffic. Many countries, such as China, the United States, Japan, Russia, and others, are heavily investing in quantum technology and research.[23] Data kept secure by companies and governments utilizing current cryptographically secure algorithms, like RSA, will no longer be viable. Without ethical guidelines in place to prevent abuse, the country with access to quantum factorization will be able to view large amounts of private information. Such risks include the anonymous and untraceable viewing of sensitive government information being transmitted between officials.

The Future

The expanding field of quantum computing has created new career and research opportunities.[24] Recently, there has been a rise of research and experimental positions in quantum information theory, quantum sensors, quantum computing theory, quantum information, machine learning in quantum information technologies, etc. Other industry titles include superconducting qubit researchers, quantum control researchers, quantum error correction researchers, quantum algorithms researchers, quantum computer architects, quantum complexity theorists, quantum cryogenic engineers, quantum microwave engineers, quantum FPGA engineers, quantum software developers, quantum community builders, and quantum user experience designers.[23] Currently, small quantum computers exist in research and experimental settings, as research-oriented devices.[25] As quantum computing technology and capabilities expand, it will likely be applied in other industries and fields. Possibilities of future applications include:
Economics and finance services:

  • Portfolio risk optimization and fraud detection, actual randomness for financial models, simulations and scenario analysis, prediction of financial crashes, etc.[23]


  • Simulations of complex molecules, the discovery of new materials, advanced molecular design, etc. [23]

Medicine and health:

  • Protein folding and drug discovery, disease detection, noninvasive and high-precision surgeries, targeted drug design, tailored medicine, prediction of therapeutic prescriptions, etc.[23]

Supply chain and logistics:

  • Optimization problems in procurement, production and distribution, vehicle routing optimization, etc.[23]

Energy and agriculture:

  • Production of ammonia, better distribution of resources, asset degradation modeling, etc.[23]


  1. Lucero, Erik [Picture of the Sycamore Chip] [Photograph]. Nature.https://www.nature.com/articles/d41586-019-03213-z
  2. Shu-Shen Li, Gui-Lu Long, Feng-Shan Bai, Song-Lin Feng, Hou-Zhi Zheng. “Quantum computing”. Proceedings of the National Academy of Sciences Oct 2001, 98 (21) 11847-11848; DOI: 10.1073/pnas.191373698
  3. Perrier, Elija. “Ethical Quantum Computing: A Roadmap.” 1Centre For Quantum Software and Information University of Technology, Sydney Sydney NSW 2000, Feb. 2021, pp. 1–10. Association for the Advancement of Artificial Intelligence, arxiv.org/pdf/2102.00759.pdf
  4. Tahan, Charles George. Silicon in the Quantum Limit: Quantum Computing and Decoherence in Silicon Architectures. 2005.
  5. Benioff, Paul. (1980). [1]. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Retrieved Mar 30, 2021.
  6. Feynman, Richard P. (1982). [2]. Simulating physics with computers. Retrieved Mar 30, 2021.
  7. Manin, Yuri. (1980). [3]. Computable and Noncomputable. Retrieved Mar 30, 2021.
  8. Jurvetson, Steve. (2019). [4]. How a quantum computer could break 2048-bit RSA encryption in 8 hours. Retrieved Mar 30, 2021.
  9. Preskill, John. Quantum Computing and the Entanglement Frontier. 2012.
  10. Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019). https://doi.org/10.1038/s41586-019-1666-5
  11. Britannica, The Editors of Encyclopaedia. "Moore's law". Encyclopedia Britannica, 26 Dec. 2019, https://www.britannica.com/technology/Moores-law. Accessed 26 March 2021.
  12. Britannica, The Editors of Encyclopaedia. "Tunneling". Encyclopedia Britannica, 24 Oct. 2016, https://www.britannica.com/science/tunneling. Accessed 26 March 2021.
  13. Holton, William Coffeen. "Quantum computer". Encyclopedia Britannica, 16 Aug. 2020, https://www.britannica.com/technology/quantum-computer. Accessed 26 March 2021.
  14. Bashuk, Mark. “Solving a Maze with a Quantum Computer.” ResearchGate, 2003, www.researchgate.net/publication/2190201_Solving_a_Maze_With_a_Quantum_Computer.
  15. “Quantum Supremacy Using a Programmable Superconducting Processor.” Google AI Blog, 23 Oct. 2019, ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html.
  16. Uk, Garciaj. “Simple Version of How RSA Works.” Hackernoon, 23 June 2017, hackernoon.com/how-does-rsa-work-f44918df914b.
  17. Simmons, Gustavus J.. "RSA encryption". Encyclopedia Britannica, 3 Aug. 2012, https://www.britannica.com/topic/RSA-encryption. Accessed 26 March 2021.
  18. Rembert, Ludovic. “Prime Factorization.” Privacy Canada, 25 Nov. 2020, privacycanada.net/mathematics/prime-factorization/.
  19. Honeyman, Alexander. "Public Key Cryptography." 19 Sept. 2019, University of Michigan, Michigan. Class lecture.
  20. B, Bobby. “How Does HTTPS Work? RSA Encryption Explained.” TipTopSecurity, 10 Sept. 2017, tiptopsecurity.com/how-does-https-work-rsa-encryption-explained/.
  21. 21.0 21.1 Möller, Matthias, and Cornelis Vuik. “On the Impact of Quantum Computing Technology on Future Developments in High-Performance Scientific Computing.” Ethics and Information Technology, vol. 19, no. 4, 2017, pp. 253–269., doi:10.1007/s10676-017-9438-0.
  22. Castellanos, Sara. “Quantum Computing Scientists Call for Ethical Guidelines.” The Wall Street Journal, Dow Jones & Company, 1 Feb. 2021, www.wsj.com/articles/quantum-computing-scientists-call-for-ethical-guidelines-11612155660.
  23. 23.0 23.1 23.2 23.3 23.4 23.5 23.6 Piattini, Mario. “ Training Needs in Quantum Computing.” aQuantum – Alarcos Research Group, University of Castilla-La Mancha Paseo De La Universidad 4, 13071, Ciudad Real, Spain, ceur-ws.org/Vol-2561/paper2.pdf
  24. Qiskit, "Expert Advice for getting a job in Quantum Computing" https://medium.com/qiskit/we-asked-experts-their-advice-for-getting-a-job-in-quantum-computing-2f55e9785a6b. 2020
  25. F. S. Grodzinsky, M. J. Wolf and K. W. Miller, "Quantum computing and cloud computing: humans trusting humans via machines," 2011 IEEE International Symposium on Technology and Society (ISTAS), Chicago, IL, USA, 2011, pp. 1-5, DOI: 10.1109/ISTAS.2011.7160598.