Difference between revisions of "Quantum Computing"

Revision as of 21:45, 14 April 2021

The Sycamore chip is composed of 54 qubits, each made of superconducting loops. ^[1]

Working on for MediaWiki 4 !!! -- 04/14/21

Quantum computers are a developing technology that today, has ramifications in any sector that is reliant on processing power or cryptographic security. They have also been creating their own sectors along with new jobs, which indicates that in the future quantum computers will contribute to the growth of all sectors.^[2] Quantum computers possess exponentially stronger computational power due to the use of quantum bits, or qubits, which compared to traditional bits, 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 ethical concerns with the capacity for such large breaches in data security to occur when quantum processing power is only accessible to the select few entities that have the means of developing this advanced technology. There are several different types of quantum computers, but the most prevalent today uses a quantum circuit model, which utilizes the quantum mechanical phenomena known as 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. ^[3]

History

Image of IBM's quantum computer Q

Quantum computing was first conceived by American physicist Paul Benioff in his paper^[4] 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^[5] and later Russian mathematician Yuri Manin suggested that quantum computers could go about completing tasks that regular computers would not be able to^[6]. 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^[7]. 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. ^[8]

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. ^[9]

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 ^[10], 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^[11] 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^[12] 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 ^[13]. 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” ^[14]. This computational power has large implications in data security, as 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 ^[15]

RSA (Rivest–Shamir–Adleman) encryption^[16] is a widely-used public-key cryptosystem that relies on the “factoring problem."^[17] 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^[18]:

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^[19].

Ethical Concerns

International abuse of power

RSA is currently being utilized worldwide under the belief that it is cryptographically secure. There are cryptographers currently working to build post-quantum secure cryptography, but there is no countermeasure to quantum computing as of yet^[20]. If one country has access to quantum computing before other countries have it, and there is no countermeasure in place, the post-quantum country has uninhibited access to a majority of the world’s internet traffic. Data kept secure by companies and governments utilizing current cryptographically secure algorithms, like RSA, are no longer 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. Sensitive government information being transmitted between officials can be seen without their knowledge.

Government on citizen

Citizen data is protected from the government as channels of communication utilize commercial companies. Businesses such as VPNs, Apple, Android, or any other third-party provider, are not required by law to release incriminating data or any data that citizens would not want the government to have. If the government were to have quantum computing capable of decrypting RSA computations, the citizens’ online traffic would no longer have to be requested from these companies. Instead, it could be immediately taken and viewed by the government. Without proper ethical guidelines to the use of quantum computing, internet use and the people’s compartmentalized data identities may be at stake. The use of the internet is implicitly anonymous to an extent; this would be challenged by the deanonymization of it via quantum factorization would result in the people’s data identities being able to be pieced together. Quantum computers will withdraw the need for citizens or companies to consent to the government viewing online transmissions.

The Future

The creation of a broad use-case usable quantum computer would be an exponential step in computational power that the world does not have the proper infrastructure to account for. This comes with ethical concerns as there are currently little or no legislative defenses or guidelines to restrict the use of a power like this. The future of data security is reliant on whether or not quantum-secure cryptography is widely established before the creation of quantum computers.

Though, even with security-related concerns, the capacity for quantum computing to change the world when properly harnessed is nearly unlimited, especially considering breakthroughs will continue being made. Uses in AI development, medical exploration, and financial optimization will inevitably be super-charged by quantum computing advances, it becomes a matter of how we go about using these technologies, not if we do. The current model of centralized control is bleak, it appears that the power of quantum computation will be in the hands of a technological elite, potentially creating a divide impossible to bridge. However, distributed systems of computing are beginning to arise, and the future for use of quantum computing may well be distributed, drawing on the will and desires of the masses for interests other than the accumulation of wealth and power. Quantum computing will slingshot us into the future. The question is: how do we align our incentives so that we are shot in the best direction?

References

1. ↑ Lucero, Erik [Picture of the Sycamore Chip] [Photograph]. Nature.https://www.nature.com/articles/d41586-019-03213-z
2. ↑ 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
3. ↑ Tahan, Charles George. Silicon in the Quantum Limit: Quantum Computing and Decoherence in Silicon Architectures. 2005.
4. ↑ 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.
5. ↑ Feynman, Richard P. (1982). [2]. Simulating physics with computers. Retrieved Mar 30, 2021.
6. ↑ Manin, Yuri. (1980). [3]. Computable and Noncomputable. Retrieved Mar 30, 2021.
7. ↑ Jurvetson, Steve. (2019). [4]. How a quantum computer could break 2048-bit RSA encryption in 8 hours. Retrieved Mar 30, 2021.
8. ↑ Preskill, John. Quantum Computing and the Entanglement Frontier. 2012.
9. ↑ 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
10. ↑ Britannica, The Editors of Encyclopaedia. "Moore's law". Encyclopedia Britannica, 26 Dec. 2019, https://www.britannica.com/technology/Moores-law. Accessed 26 March 2021.
11. ↑ Britannica, The Editors of Encyclopaedia. "Tunneling". Encyclopedia Britannica, 24 Oct. 2016, https://www.britannica.com/science/tunneling. Accessed 26 March 2021.
12. ↑ Holton, William Coffeen. "Quantum computer". Encyclopedia Britannica, 16 Aug. 2020, https://www.britannica.com/technology/quantum-computer. Accessed 26 March 2021.
13. ↑ Bashuk, Mark. “Solving a Maze with a Quantum Computer.” ResearchGate, 2003, www.researchgate.net/publication/2190201_Solving_a_Maze_With_a_Quantum_Computer.
14. ↑ “Quantum Supremacy Using a Programmable Superconducting Processor.” Google AI Blog, 23 Oct. 2019, ai.googleblog.com/2019/10/quantum-supremacy-using-programmable.html.
15. ↑ Uk, Garciaj. “Simple Version of How RSA Works.” Hackernoon, 23 June 2017, hackernoon.com/how-does-rsa-work-f44918df914b.
16. ↑ Simmons, Gustavus J.. "RSA encryption". Encyclopedia Britannica, 3 Aug. 2012, https://www.britannica.com/topic/RSA-encryption. Accessed 26 March 2021.
17. ↑ Rembert, Ludovic. “Prime Factorization.” Privacy Canada, 25 Nov. 2020, privacycanada.net/mathematics/prime-factorization/.
18. ↑ Honeyman, Alexander. "Public Key Cryptography." 19 Sept. 2019, University of Michigan, Michigan. Class lecture.
19. ↑ B, Bobby. “How Does HTTPS Work? RSA Encryption Explained.” TipTopSecurity, 10 Sept. 2017, tiptopsecurity.com/how-does-https-work-rsa-encryption-explained/.
20. ↑ 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.