An Introduction to Quantum Computing: Superposition, Qubits, Algorithms, and Challenges

Recently, Associate Researcher Zhang Wenzhuo from the Shanghai Institute of USTC (CAS Quantum Information and Quantum Technology Frontier Innovation Center) wrote an article on quantum computing that was published on Guokr.

The author notes that this is currently the most accessible article on quantum technology and its applications.

China Academy of Sciences and Alibaba have jointly established the "CAS‑Alibaba Quantum Computing Laboratory" at the Shanghai Institute of USTC, marking the first time a Chinese research institution has received full private capital funding for basic scientific research.

CAS and Alibaba jointly established a quantum computing laboratory. Image source: Xinhua News

Globally, similar collaborations began in the United States: after IBM and Microsoft, Google started quantum computing research and co‑founded the Quantum Artificial Intelligence Lab (QuAIL) with NASA. In 2014 Google hired John Martinis from UC Santa Barbara to create a superconducting quantum computing lab, pioneering fully private funding of such a lab.

Alibaba, China’s largest internet company, brings strong classical IT expertise, while USTC leads in quantum information research; inspired by Google’s model, they formed this joint laboratory.

Quantum Superposition

Quantum computing’s appeal stems from the most fundamental and strange quantum property—superposition. In classical physics an object has a single definite state at a given moment, whereas quantum mechanics allows a particle to exist in multiple states simultaneously, as illustrated by the double‑slit experiment.

Classical information technology relies on bits that are either 0 or 1. A quantum bit (qubit) can be a superposition of 0 and 1, expressed as:

|Φ> = a|0> + b|1>

Here, “Φ” denotes the superposition, “| >” is Dirac notation for a quantum state, and a and b are complex numbers satisfying |a|² + |b|² = 1. A qubit can be visualized on a Bloch sphere, where unlike a classical bit’s two discrete points, a qubit’s state occupies infinitely many points on the sphere’s surface.

Bloch sphere representation of a qubit. Image source: Wikipedia

Because a qubit is in superposition, a single operation affects both |0⟩ and |1⟩ simultaneously. Extending this, a 10‑qubit register can represent 2¹⁰ = 1024 different numbers at once, allowing a quantum computer to process all 1024 possibilities in a single step.

The computational power grows exponentially with the number of qubits; a 64‑qubit machine could handle 2⁶⁴ ≈ 1.84×10¹⁹ values simultaneously. If such a machine operated at 1 GHz, its processing speed would exceed the world’s fastest supercomputer by over 5×10⁵ times.

This genuine parallelism, unlike classical parallel processing that merely adds more CPUs, makes quantum computers highly attractive for big‑data workloads.

Shor Algorithm – The End of RSA Encryption

In 1985 David Deutsch proposed the quantum Turing machine concept, and in 1995 Peter Shor introduced the first quantum algorithm that solves a concrete problem: integer factorization.

RSA encryption, which underpins most online security, relies on the difficulty of factoring large numbers into prime components. Classical computers cannot factor such numbers in a feasible time.

Shor’s algorithm exploits quantum parallelism to factor large numbers quickly, effectively breaking RSA encryption.

While quantum computers threaten cryptographic schemes based on computational hardness, quantum communication—its “twin”—offers fundamentally secure information transfer.

Grover Algorithm – The Future Search Engine

One year after Shor’s breakthrough, Lov Grover proposed an algorithm that uses quantum parallelism to search an unsorted database with quadratically fewer steps than any classical algorithm.

Grover’s quantum search dramatically outpaces classical data search, explaining why internet giants are keenly interested in quantum computing for next‑generation search engines.

Decoherence – The Biggest Obstacle

Although quantum algorithms have been theoretically mature for years, building the first practical quantum computer remains distant because maintaining coherent quantum states across many qubits is extremely difficult.

Decoherence occurs when environmental interactions disturb quantum states, causing them to collapse into classical states. Larger systems experience more interactions, leading to faster decoherence, which is why macroscopic objects like Schrödinger’s cat cannot exhibit observable superposition.

Physical implementations vary: ion‑trap and NMR systems can sustain longer coherence times but scale poorly, while superconducting circuits and quantum dots allow larger qubit counts at the cost of very short coherence times. The latter approach currently appears more promising for achieving usable quantum computers.

Superconducting quantum chip funded by Google. Image source: University of California, Santa Barbara

Quantum Computers and Artificial Intelligence

Physicist Roger Penrose argued that the human brain cannot be modeled as a deterministic classical computer; instead, quantum measurement could provide the randomness and global processing that classical pixel‑by‑pixel computation lacks, proposing that the brain functions as a quantum computer.

However, MIT physicist Max Tegmark calculated that Penrose’s quantum‑brain model would decohere in 10–15 seconds at room temperature, far too short for meaningful computation, leaving the hypothesis unproven. Nonetheless, quantum computers might eventually illuminate the intersection of quantum and classical processes, shedding light on consciousness and enabling true artificial intelligence.

In summary, once realized, quantum computers could become one of humanity’s greatest scientific achievements. Their development remains costly and uncertain, but history shows that long‑term, heavily funded research (e.g., Bell Labs) eventually yields transformative technologies. Future generations may use quantum‑enabled smartphones and intelligent robots, thanking today’s investment by internet giants.

References

1. D. Deutsch, “Quantum Theory, the Church‑Turing principle and the universal quantum computer”, Proc. R. Soc. Lond. A, 400, 97 (1985).

2. P. W. Shor, “Polynomial‑Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, http://arxiv.org/pdf/quant‑ph/9508027.

3. L. K. Grover, “A fast quantum mechanical algorithm for database search”, http://arxiv.org/pdf/quant‑ph/9605043v3.

4. J. I. Cirac and P. Zoller, “Quantum computation with cold trapped ions”, Phys. Rev. Lett., 74, 4091 (1995).

5. J. M. Martinis, “Superconducting Phase Qubits”, Quantum Information Processing 8, 81 (2009).

This article was originally reposted from Guokr.com.