The Genesis of Quantum Computing

The Beginning of Quantum Computing

The beginning of quantum computing can be traced to physicists Richard Feynman and David Deutsch. In 1981, Feynman suggested that classical computers might not be able to efficiently simulate quantum systems due to the inherent complexity of quantum mechanics. He proposed that the idea of quantum-based computers be used to simulate quantum systems.

Then in 1985, David Deutsch made Feynman’s abstract ideas concrete when he published the seminal paper, Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. This paper introduced the concept of a universal quantum computer, a theoretical computing machine that uses the principles of quantum mechanics to perform calculations. Such a computer would be capable of solving any computational problem that a classical computer can solve, and can also efficiently solve certain problems that are currently intractable for classical computers.

TL;DR of the paper:

1. Church-Turing Principle:

   • The classical Church-Turing principle asserts that any function which can be computed by any "effectively calculable" means can be computed by a Turing machine.

   • Deutsch extends this to quantum theory, proposing that any physical process governed by quantum mechanics can be simulated by a quantum computer.

2. Quantum Computation:

   • Deutsch introduces the idea of a quantum Turing machine (QTM), a theoretical model of a quantum computer. A QTM uses quantum bits (qubits) and can perform computations using quantum superposition and entanglement.

   • He describes how a QTM can perform any computation that a classical Turing machine can, but also solve certain problems more efficiently by exploiting quantum parallelism.

3. Universal Quantum Computer:

   • A universal quantum computer, as proposed by Deutsch, is capable of simulating any physical process. This is more powerful than classical computers, which struggle with simulating quantum systems due to exponential growth in complexity.

   • Deutsch shows that a universal quantum computer could, in theory, simulate any other quantum system, making it a powerful tool for understanding and predicting quantum phenomena.

4. Quantum Parallelism:

   • The paper discusses how quantum computers can process multiple inputs simultaneously due to superposition, a feature not possible in classical computing.

   • This parallelism provides an exponential speedup for certain algorithms, such as factoring large numbers, which has profound implications for cryptography.

5. Implications for Computation and Physics:

   • Deutsch’s work suggests that the physical world itself operates according to quantum information principles, and understanding these principles is essential for advancing computational theory.

   • The paper implies that the future of computing lies in harnessing quantum mechanics, potentially revolutionizing fields that rely on complex computations.

Learning Quantum Computing

• Short 6 minute high-level introduction to Quantum Computing by Veritasium (link)

• Quantum Computing Course - Math and Theory for Beginners by freecodecamp.org (link)

• San Jose State’s course: Quantum Computing Hardware and Architecture (EE274 SJSU) (link)

• Programming quantum computers using Qiskit (IBM’s quantum computing SDK) (link)

Growth of Quantum Computing

• The market for quantum computing is estimated to grow from $1.16 billion in 2024 to $12.6 billion in 2032, a CAGR of 34.8%

• By 2022, according to McKinsey, China spent $15.3 billion on quantum computing initiatives, compared to the EU’s $7.2 billion, the US’s $1.9 billion and Japan’s $1.8 billion

• Government spending is increasing in quantum technology as it is seen as a national security issue by most nations

• IonQ, the largest publicly traded quantum computing company with $1.78 billion market capitalization, lists 57 jobs on its site