- \n
- On hidden realities (part 1) – Many-worlds interpretation of quantum mechanics<\/a><\/li>\n
- On hidden realities (part 2) – Space-time geometries and dynamics<\/a><\/li>\n
- On hidden realities (part 3) – Higher dimensional universes<\/a><\/li>\n
- On hidden realities (part 4) – Holographic principle<\/a><\/li>\n
- On hidden realities (part 5) – Simulated reality<\/a><\/li>\n<\/ul>\n
So, I think it’s about time to get (a little) deeper about the basis of quantum computing !<\/p>\n
![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/quantum-physics-formulas-over-blackboard.jpg\")
<\/p>\nWhat is quantum computing ?<\/strong><\/p>\n
In simple terms, a quantum computer is any device that uses quantum mechanical phenomena, such as superposition<\/a> or entanglement<\/a> to perform calculations or manipulate data.<\/p>\n
Whereas common computing requires the data to be encoded into binary digits (known as bits), each of which is always in one of two definite states (0 or 1), quantum computation uses quantum bits (known as qubits), which are superpositions of quantum states.<\/p>\n
Quantum computing is still in its infancy. Experiments have been carried out in which operations are executed on a very small number of quantum bits (Google’s Bristlecone 72 qubits processor being the record as of 2018). Practical and theoretical research are carried on, in effort to develop quantum computers for civilian, business, trade, environmental and security purposes, such as cryptanalysis.<\/p>\n
Quantum computing typically aims at solving certain classes of problems (like integer factorization) quicker than any classical computers or simulating multi-body quantum systems. Indeed, there exist quantum algorithms<\/a>, such as Simon’s algorithm<\/a>, that run faster than any possible probabilistic classical algorithm.<\/p>\n
It is worth noting that a classical computer could in principle (with exponential resources) simulate a quantum algorithm, as quantum computation does not violate the Church\u2013Turing thesis<\/a>.<\/sup> On the other hand, quantum computers may be able to efficiently solve problems which are not practically <\/strong>feasible on classical computers.<\/p>\n
Quantum computing is of great importance for cryptography and cryptanalysis. Typically, RSA public key encryption relies on the difficulty of factoring large integers. It is conjectured that factorization is impossible to do efficiently with a classical computer. Shor’s factoring algorithm<\/a> for quantum computers would render this encryption method useless.<\/p>\n
Quantum information<\/strong><\/p>\n
In quantum computing, a quantum bit (or qubit) is a unit of information. It is modeled as a common two-state quantum-mechanical system<\/a>.<\/p>\n
In a classical system, a bit would have to be either in one state or the other. In a quantum system, a qubit can be a superposition of both states at the same time, a property that is fundamental to quantum computing.<\/p>\n
Let’s enter the realm of quantum mechanics. As we have seen<\/a>, a quantum state can be mathematically described an element of a Hilbert vector space<\/a>. Following Dirac’s notation, a quantum state (or ket) will denoted as
.<\/p>\n
Let’s introduce the following vectors
and
.<\/p>\n
A pure state qubit would be represented as a linear combination<\/a> of
and
:<\/p>\n
where
and
are probability amplitudes<\/a>.<\/p>\n
Because the absolute squares of amplitudes
and
are probabilities, it follows that the complex numbers
, which can be treated as the equation for a 3-sphere embedded in 4-dimensional space with a radius of 1, called a Bloch sphere<\/a>:
\n<\/span><\/p>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/blochsphere.png\")
<\/p>\nOperators act on quantum states. More specifically, observables<\/a> are self-adjoint<\/a> hermitian<\/a> operators.<\/p>\n
Measurement is an operation in which information is gained about the state of the qubit. The result of the measurement of the pure quantum state
will either be
or
, with respective probabilities
.<\/p>\n
Classical computation<\/strong><\/p>\n
Now, let’s get back for a moment to non-quantum computing. Computation is done by means of an algorithm, which can be thought of as a set of instructions for solving a specific problem.<\/p>\n
Around 1936-37, the great mathematician, logician, computer scientist, cryptanalyst, philosopher, and theoretical biologist Alan Turing<\/a> devised a hypothetical machine that could execute any algorithm called … a Turing Machine<\/a>.<\/div>\n<\/div>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/turingmachine.png\")
<\/div>\nA Turing machine consists of:<\/div>\n<\/div>\n- \n
- A tape<\/strong>, divided into cells. Each cell contains a symbol from some finite alphabet. The tape is assumed to be arbitrarily extendable to the left and to the right.<\/li>\n
- A head<\/strong>, that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time.<\/li>\n
- A state register<\/strong> that stores the (finate) state of the machine.<\/li>\n
- A (finite) table<\/strong> of instructions that, given the state (qi<\/sub><\/em>) the machine is currently in and the symbol (aj<\/sub><\/em>) it is reading on the tape (symbol currently under the head), tells the machine what to do: erase or write a symbol, move the head, …<\/li>\n<\/ul>\n
Programs are defined by a set of instructions. An instruction can be written as T:(q,a)<\/em> \u2192 (q’,a’,d)<\/em>, where q<\/em> is the current state and q’<\/em> is the final state of the head, a<\/em> is the symbol in the cell, a’<\/em> is the symbol to be written, d<\/em> is the direction the head will move.<\/div>\n<\/div>\n\n\nThe input is the initial state of the Turing machine.The output of a Turing machine is the final state of the Turing machine (if any). For a Turing machine it is impossible to know for all inputs whether the control head will reach a halting state or not. This is the known as the halting problem<\/a>.<\/p>\n
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine<\/a>. A more mathematically oriented definition with a similar “universal” nature was introduced by Alonzo Church<\/a>, whose work on lambda calculus<\/a> intertwined with Turing’s in a formal theory of computation<\/a> known as the Church\u2013Turing thesis.<\/p>\n<\/div>\n
The thesis conjectures that any function whose values can be computed by an algorithm<\/a> can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine.<\/p>\n<\/div>\n
These principles are considered to be the origin of the idea of a stored-program computer used by John von Neumann<\/a> in 1946 for the “Electronic Computing Instrument<\/em>” that now bears his name: the von Neumann architecture.<\/a><\/p>\n
Logic gates<\/strong><\/p>\n
Logic gates is an idealized or physical device implementing a Boolean function. A logic gate performs a logical operation on one or more binary inputs and produces a binary output. In any computation, a circuit (made of logic gates) can be represented as mapping a n-bit input to a m-bit output.<\/p>\n
The following table lists such logic gates:<\/p>\n
- A head<\/strong>, that can read and write symbols on the tape and move the tape left and right one (and only one) cell at a time.<\/li>\n
- On hidden realities (part 2) – Space-time geometries and dynamics<\/a><\/li>\n
![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/NOT.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/AND.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/OR.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/NAND.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/NOR.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/XOR.png\")
<\/td>\n
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/XNOR.png\")
<\/td>\n
<\/td>\n
<\/p>\n
<\/p>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/binaryaddition.png\")
<\/p>\n
<\/div>\n<\/div>\n
and 
<\/p>\n
or 
<\/div>\n
<\/li>\n
<\/li>\n
<\/li>\n
<\/li>\n<\/ul>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/qubits-superposition.png\")
<\/div>\n
<\/div>\n
<\/div>\n
) of measuring either 
or 
.<\/span><\/span><\/div>\n
<\/span><\/span> or 
<\/span><\/span>.<\/div>\n
<\/li>\n
<\/li>\n
<\/li>\n<\/ul>\n
,<\/p>\n
<\/li>\n
<\/li>\n
<\/li>\n
<\/li>\n<\/ul>\n
<\/p>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/qHadamard_gate..png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/Qcircuit_NOT.png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/Qcircuit_SqrtNot.png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/qSwap_gate.png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/qSqrtSwap.png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/qCNOT_gate.png\")
<\/td>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/QFTn.png\")
<\/p>\n
takes n-digit binary values as input and produces either a 0 or a 1 as output for each such value.<\/p>\n
is constant (0 on all outputs or 1 on all outputs) or balanced (returns 1 for half of the input domain and 0 for the other half) by using the oracle.<\/p>\n
from 
has to be a quantum oracle which doesn’t decohere ![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/deutsch-algo.png\")
<\/p>\n![\"\"](\"https:\/\/www.quantum-bits.org\/wp-content\/uploads\/2018\/03\/shor-algo.png\")
<\/p>\n