Quantum Computing Course

Richard P. Feynman is regarded as the person who sparked the idea of a quantum computer with his talk titled "There is Plenty of Room at the Bottom" given at the American Physical Society in Pasadena (December 1959).

A transcript from his talk "There's Plenty Room at the Bottom" conveys Feynman's physical notion of information storage from a volumetric perspective and depicts DNA as an example, where "around 50 atoms are used for one bit of information about the cell". Then Feynman describes how small computers could be built and fabricating electric circuits on the atomistic level although resistance would be a problem. The problem, Feynman mentions, could be solved through the use of superconductivity. At this scale, building a computer with atoms becomes quantum mechanically defined and "We can use, not just circuits, but some system involving the quantized energy levels, or the interactions of quantized spins, etc.". Although Feynman does not use the term "quantum computer" one can already see the vision and follow the line of thought he had.

David Finkelstein acknowledged in his "Space-time Structure in High Energy Interactions" article that it was Feynman who introduced him to the idea that space-time should be quantum mechanically discretized and in this way a "reasonable model for the world is a computer, a giant digital computer" would allow more advanced computations.

In 1979 Paul Benioff constructed a quantum mechanical model of computers where the evolution of a Hamiltonian (energy function) would represent a closed conservative system. Benioff showed in the article "The computer as a physical system: a microscopic quantum mechanical hamiltonian model of computers as represented by Turing machines" that this quantum mechanical model can be calculated by a set of Turing machines which themselves are stationary systems, but collectively, these processing units can simulate dynamic systems.

Richard Feynman's description of how to accurately calculate quantum physical systems on a quantum computer architecture can be seen as the first description of a quantum computer architecture. He submitted the description on the 7th of May 1981 to the International Journal of Theoretical Physics. The article was then published in volume 21, June, 1982. Together with Richard Feynman, David Deutsch is regarded as the father of the idea and detailed description of a quantum computer. David Deutsch described in 1985 his idea of an universal quantum computer. In the proceedings paper "The church–turing principle and the universal quantum computer" he describes a computing machine with a quantum physical architecture and that it can have many remarkable properties which cannot be found in Turing machines. Further, David Deutsch proved also with the Deutsch and Deutsch-Josza algorithm that a quantum computer can give an advantageous speed up in comparison to a classical computing scheme.

Quantum supremacy and quantum advantage

Quantum computing has been studied for decades and ranges from information theory to hardware technologies, computational models implemented on specific hardware types which go hand in hand with the mathematical problem formulations being solved on the quantum device.

It has applications in nearly every field that contains or utilizes computations with high complexity. Quantum computers have the potential to impact many aspects of current domains of science, including computer science, mathematics, and chemical engineering. Generally, to compare the performance of classical computing and quantum computing is not an easy task and several scenarios exist how a quantum computer could be utilized for the benefit of research or solving societal important problems which a classical computer alone could not solve due to the problem's NP-hard complexity.

A desirable scenario is one where problems that can not be solved by classical computers in any feasible amount of time, would be possibly solved with a quantum computer. This is one of the main goals of quantum computing, which is termed quantum supremacy. It is a demonstration that a programmable quantum device can solve a problem that any existing or future classical computer is not able to solve due to the problem's NP-hard complexity.

A second scenario is related to computational problems which could be solved more efficiently with both classical computers and quantum computers together, although not ruling out that a classical algorithm could solve the problem as efficienctly as the hybrid classical-quantum scheme when more powerful classical processing units would be available or a better classical algorithm is discovered.

The third category is comprised of problems that can not be solved more efficiently with a quantum computer. Thus, a careful analysis of the mathematical complexity of a mathematical problem formulation must be made to assess which computational system/architecture should be applied.

John Preskill published a paper titled "Quantum computing and the entanglement frontier" in November 2012 about quantum supremacy and the consequences it will have to several critical applications in society such as cryptography and optimization.

In October 2019, Google claimed with the Nature article "Quantum supremacy using a programmable superconducting processor" to have achieved supremacy with a quantum processor called "Sycamore" to sample the output of a pseudo-random quantum circuit. They used 53 qubits to represent a dimensional state space.

Measurements from repeated quantum experiments sampled the resulting probability distribution, which then was verified using classical simulations. The process of sampling one instance of a quantum circuit a million times took about 200 seconds. With a classical computer that process would have taken 10,000 years. However, IBM stated with the blog post 'On "quantum supremacy"' that the computation of the Google experiment could be performed on a classical computer in 2.5 days. Many more quantum supremacy claims and demonstrations were made and the below table gives an overview of some of them.

You can learn more about quantum computing for chemistry topics by signing up for the Dashboard Quantum or Machine Learning subscriptions.