## Abstract

It now appears that quantum computers are poised to enter the world of computing and establish its dominance, especially, in the cloud. Turing machines (classical computers) tied to the laws of classical physics will not vanish from our lives but begin to play a subordinate role to quantum computers tied to the enigmatic laws of quantum physics that deal with such non-intuitive phenomena as superposition, entanglement, collapse of the wave function, and teleportation, all occurring in Hilbert space. The aim of this 3-part paper is to introduce the readers to a core set of quantum algorithms based on the postulates of quantum mechanics, and reveal the amazing power of quantum computing.

**Key words**: Quantum mechanics, quantum computing, quantum algorithms.

## Part I – Foundations

In Part 1 we introduce certain fundamental differences between classical and quantum physics. They lead to vastly different means of computing. Indeed, the very idea of the state of a system in quantum mechanics is conceptually different from its classical counterpart. In each, states are represented by different mathematical objects and have a different logical structure. In classical physics, the state of a system describes everything that is required to predict the future of that system. It is not so for a quantum system. The state of a quantum system is neither completely measurable nor completely predictable. We conclude this part by describing a set of quantum operators and their essential features that enable quantum computing by exploiting such exotic quantum features as superposition, entanglement, and collapse of the wave function. Part I comprises Sections 1-8 of the paper. In Part II comprising Sections 9-11, we will describe a range of quantum algorithms to display the tremendous computing power waiting to be unleashed via controlled superposition and entanglement of quantum states, and collapse of the wave function. In Part III we speculate on the quantum measurement conundrum and comment on the future of quantum computing.

## 1.Introduction

Caution:Leave your intuition and common sense behind. Ask not what quantum computing can do for you, ask what you can do for quantum computing. You are about to enter a world where disbelief reigns.

Scientific discoveries are based on conjectures and refutations^{2}. It will always remain so. As of now, quantum theory contains our most fundamental knowledge of the physical world. It is a very different description of Nature from classical physics described by Galileo, Newton, Maxwell, and Einstein. A law of Nature states what is possible within certain inviolable boundaries.

I expect readers, not trained in quantum mechanics, to be confused, especially if they have heard such weird stories as a cat being simultaneously dead and alive, the phenomenon of teleportation, a photon or an electron concurrently traveling along two paths, and so on. Rest assured even established researchers in quantum mechanics struggle to develop an intuition about the subject. Einstein once remarked, Quantum Mechanics: Real Black Magic Calculus. And Niels Bohr said, *“If quantum mechanics hasn’t profoundly shocked you, you haven’t understood it yet.”*

It pays to view quantum mechanics as a mathematical framework for constructing physical theories and concentrate on grasping the rules of the game. Explore the subject as if trying to understand an alien world. Patience and diligence will be handsomely rewarded because what will be revealed is the finest set of scientific conjectures created by the human mind to date.

As a deeper understanding of Nature via physics evolved so did the mathematical complexity of the Laws of Nature that describe it in the sense that mental visualization by means of interpreting those abstractions has become increasingly difficult. Later laws have generally required more sophisticated (abstruse) mathematics, which has placed a heavy burden on people trying to understand Nature. Indeed, “it is impossible to explain honestly the beauties of the laws of nature in a way that people can feel, without their having some deep understanding of mathematics.”^{4}. We communicate through language and emotion. Benjamin Lee Whorf (1897– 1941) said, *“Language shapes the way we think, and determines what we can think about.”* And Ludwig Wittgenstein (1889 –1951) said, *“The limits of my language mean the limits of my world.”* It is more so with mathematics because it is both a language and a tool for reasoning. It also requires extreme mental discipline and meticulous training. It is amazing that as mathematics continued to enrich itself through new explorations (e.g., calculus, fractal geometry, etc.) it also enabled physicists expand their understanding of Nature.

So, keep a standard text book on mathematics nearby for ready reference (e.g., Kreyszig^{5}, Chapters 7-12). A good understanding of linear algebra and Fourier analysis is necessary. Further, abandon common sense like the plague. Just stick to the postulates of quantum mechanics and their underlying mathematics. Do not add or subtract unless you want to rewrite quantum mechanics.

## 2.The universal Turing machine (UTM)

The remarkable, 1936 paper by Alan Turing^{6} provides a mathematical description of all classical computers—from Charles Babbage’s analytical engine^{7} to the supercomputers of today—known as the Universal Turing Machine (UTM). It was conceived before there were any real computers. The UTM perfectly mimics an unintelligent person, who tirelessly and with absolute concentration, performs calculations as instructed, in a step-by-step manner, i.e., according to a given algorithm. This Turing Person has at its disposal unlimited time, paper, pencil, and energy. Note that the UTM does only those tasks that a human might do in executing an algorithm without the help of insight. There is a strong belief, so far unrefuted, among computer scientists that what is human-computable is machine-computable. This is the famous Church-Turing Thesis: “The class of functions computable by a Turing machine corresponds exactly to the class of functions which we would naturally regard as being computable by an algorithm.”^{8} It is also a statement about the limitations of the human mind.

Through mathematical abstraction, Turing captured the essence of algorithmic processes and ushered in the modern computer revolution. He thus revealed a very mechanistic aspect of reality that there may be nothing more to mind, brain, or the physical world than ceaseless computation. Max Tegmark expresses this idea even more explicitly: *“Our reality isn’t just described by mathematics – it is mathematics … Not just aspects of it, but all of it, including you.”* In other words,* “our external physical reality is a mathematical structure”*^{10}. One might thus conclude the Universe is a computer and hence the Laws of Nature must be computable. While a physical UTM does use quantum processes, its actual construction, by design, suppresses all quantum effects.

^{[2] }Popper (1963).

^{[3] }As quoted in Vizzotto, Altenkirch, & Sabry (2005).

** ^{[4] }Feynman (1965), pp. 33-34.**

^{[5] }Kreyszig (2011).

^{[6] }Turing (1936).

^{[7] }Charles Babbage (1791-1871) was Lucasian Professor of mathematics at Cambridge from 1828 to 1839. He was the first to describe a programmable computer.

^{[8] }Nielsen & Chuang (2000), p. 125.

^{[9] }Aaronson (2013).

^{[10] }Tegmark (2014), p. 254.