Sources Mosca, Hayes, Ekert,
Lee Spector
in collaboration with
Herbert J. Bernstein, Howard Barnum, Nikhil Swamy
{lspector, hbernstein, hbarnum, nikhil_swamy}@hampshire.edu}
School of Cognitive Science, School of Natural Science
Institute for Science and Interdisciplinary Studies (ISIS)
Hampshire College Origin of slides: John Hayes, Peter Shor, Martin Lukac, Mikhail Pivtoraiko, Alan Mishchenko, Pawel Kerntopf, Mosca, Ekert

Introduction :

Introduction Short-Term Objectives
Long-Term Objectives
Prerequisite Introduce Quantum Computing Basics to interested students at KAIST. Especially non-physics students Engage into AI/CS/Math Research projects benefiting from Quantum Computing. Continue our previous projects in quantum computing - No linear algebra or quantum mechanics assumed
- A ECE, math, physics or CS background would be beneficial, practically-oriented class.

Introduction :

Introduction MainTextbook Quantum Computation &
Quantum Information
Michael A. Nielsen
Isaac L. Chuang
ISBN: 0 521 63503 9 Paperback
ISBN: 0 521 63235 8 Hardback
Cost: $48.00 New Paperback
$35.45 Used Paperback
(http://www.amazon.com)
also in KAIST bookstore

Presentation Overview :

Presentation Overview Qubits Quantum
Computation Quantum
Circuits Quantum
Algorithms Quantum
Information
Processing 1 Qubit -> Bloch Sphere,
2 Qubits -> Bell States,
n Qubits Gates: Single Qubit, Arbitrary Single Qubit -> Universal
Quantum Gates, Multiple Qubit Gates -> CNOT
Other Computational Bases Qubit Swap Circuit
Qubit Copying Circuit
Bell State Circuit -> Quantum Teleportation Toffoli Gate -> Quantum Parallelism -> Hadamard Transform
Deutsch's Algorithm, Deutsch-Josa Algorithm
Other Algorithms
– Fourier Transform, Quantum Search, Quantum Simulation Stern-Gerlach, Optical Techniques, Traps, NMR, Quantum Dots

Historical Background and Links :

Historical Background and Links Quantum
Computation
&
Quantum
Information Computer
Science Information
Theory Cryptography Quantum
Mechanics Study of information processing tasks that can be accomplished using quantum mechanical systems Digital
Design

Slide 7:

What will be discussed? Background
Quantum circuits synthesis and algorithms
Quantum circuits simulation
Quantum Computation
AI for quantum computation
Quantum computation for AI
Quantum logic emulation and evolvable hardware
Quantum circuits verification
Quantum-based robot control

What is quantum computation? :

What is quantum computation? Computation with coherent atomic-scale dynamics.
The behavior of a quantum computer is governed by the laws of quantum mechanics.

Why bother with quantum computation? :

Why bother with quantum computation? Moore’s Law: We hit the quantum level 2010~2020.
Quantum computation is more powerful than classical computation.
More can be computed in less time—the complexity classes are different!

The power of quantum computation :

The power of quantum computation In quantum systems possibilities count, even if they never happen!
Each of exponentially many possibilities can be used to perform a part of a computation at the same time.

Nobody understands quantum mechanics :

Nobody understands quantum mechanics “No, you’re not going to be able to understand it. . . . You see, my physics students don’t understand it either. That is because I don’t understand it. Nobody does. ... The theory of quantum electrodynamics describes Nature as absurd from the point of view of common sense. And it agrees fully with an experiment. So I hope that you can accept Nature as She is -- absurd.
Richard Feynman

Absurd but taken seriously (not just quantum mechanics but also quantum computation) :

Absurd but taken seriously (not just quantum mechanics but also quantum computation) Under active investigation by many of the top physics labs around the world (including CalTech, MIT, AT&T, Stanford, Los Alamos, UCLA, Oxford, l’Université de Montréal, University of Innsbruck, IBM Research . . .)
In the mass media (including The New York Times, The Economist, American Scientist, Scientific American, . . .)
Here.

Slide 13:

Quantum Logic Circuits

A beam splitter :

A beam splitter Half of the photons leaving the light source arrive at detector A;
the other half arrive at detector B.

A beam-splitter :

A beam-splitter The simplest explanation is that the beam-splitter acts as a classical coin-flip, randomly sending each photon one way or the other.

An interferometer :

An interferometer Equal path lengths, rigid mirrors.
Only one photon in the apparatus at a time.
All photons leaving the source arrive at B.
WHY?

Possibilities count :

Possibilities count There is a quantity that we’ll call the “amplitude” for each possible path that a photon can take.
The amplitudes can interfere constructively and destructively, even though each photon takes only one path.
The amplitudes at detector A interfere destructively; those at detector B interfere constructively.

Calculating interference :

Calculating interference Arrows for each possibility.
Arrows rotate; speed depends on frequency.
Arrows flip 180o at mirrors, rotate 90o counter-clockwise when reflected from beam splitters.
Add arrows and square the length of the result to determine the probability for any possibility.

Double slit interference :

Double slit interference

Quantum Interference : Amplitudes are added and not intensities ! :

Quantum Interference : Amplitudes are added and not intensities !

Interference in the interferometer :

Interference in the interferometer

Quantum Interference :

Quantum Interference The simplest explanation must be wrong, since it would predict a 50-50 distribution.

More experimental data :

More experimental data

A new theory :

A new theory The particle can exist in a linear combination or superposition of the two paths

Probability Amplitude and Measurement :

Probability Amplitude and Measurement If the photon is measured when it is in the state then we get with probability and |1> with probability of |a1|2

Quantum Operations :

Quantum Operations The operations are induced by the apparatus linearly, that is, if
and
then

Quantum Operations :

Quantum Operations Any linear operation that takes states
satisfying
and maps them to states
satisfying
must be UNITARY

Linear Algebra :

Linear Algebra is unitary if and only if

Linear Algebra :

Linear Algebra corresponds to corresponds to corresponds to

Linear Algebra :

Linear Algebra corresponds to corresponds to

Linear Algebra :

Linear Algebra corresponds to

Abstraction :

Abstraction The two position states of a photon in a Mach-Zehnder apparatus is just one example of a quantum bit or qubit Except when addressing a particular physical implementation, we will simply talk about “basis” states and
and unitary operations like
and

Slide 33:

where corresponds to and corresponds to

Slide 34:

An arrangement like is represented with a network like

More than one qubit :

More than one qubit If we concatenate two qubits we have a 2-qubit system with 4 basis states and we can also describe the state as
or by the vector 1

More than one qubit :

More than one qubit In general we can have arbitrary superpositions where there is no factorization into the tensor product of two independent qubits.
These states are called entangled.

Entanglement :

Entanglement Qubits in a multi-qubit system are not independent—they can become “entangled.”
To represent the state of n qubits we use 2n complex number amplitudes.

Measuring multi-qubit systems :

Measuring multi-qubit systems If we measure both bits of
we get with probability

Measurement :

Measurement ||2, for amplitudes of all states matching an output bit-pattern, gives the probability that it will be read.
Example:
0.316|00› + 0.447|01› + 0.548|10› + 0.632|11›
The probability to read the rightmost bit as 0 is |0.316|2 + |0.548|2 = 0.4
Measurement during a computation changes the state of the system but can be used in some cases to increase efficiency (measure and halt or continue).

Classical Versus Quantum :

Classical Versus Quantum

Classical vs. Quantum Circuits :

Goal: Fast, low-cost implementation of useful algorithms using standard components (gates) and design techniques
Classical Logic Circuits
Circuit behavior is governed implicitly by classical physics
Signal states are simple bit vectors, e.g. X = 01010111
Operations are defined by Boolean Algebra
No restrictions exist on copying or measuring signals
Small well-defined sets of universal gate types, e.g. {NAND},{AND,OR,NOT}, {AND,NOT}, etc.
Well developed CAD methodologies exist
Circuits are easily implemented in fast, scalable and macroscopic technologies such as CMOS Classical vs. Quantum Circuits

Classical vs. Quantum Circuits :

Quantum Logic Circuits
Circuit behavior is governed explicitly by quantum mechanics
Signal states are vectors interpreted as a superposition of binary “qubit” vectors with complex-number coefficients
Operations are defined by linear algebra over Hilbert Space and can be represented by unitary matrices with complex elements
Severe restrictions exist on copying and measuring signals
Many universal gate sets exist but the best types are not obvious
Circuits must use microscopic technologies that are slow, fragile, and not yet scalable, e.g., NMR Classical vs. Quantum Circuits

Quantum Circuit Characteristics :

Unitary Operations
Gates and circuits must be reversible (information-lossless)
Number of output signal lines = Number of input signal lines
The circuit function must be a bijection, implying that output vectors are a permutation of the input vectors
Classical logic behavior can be represented by permutation matrices
Non-classical logic behavior can be represented including state sign (phase) and entanglement Quantum Circuit Characteristics

Quantum Circuit Characteristics :

Quantum Measurement
Measurement yields only one state X of the superposed states
Measurement also makes X the new state and so interferes with computational processes
X is determined with some probability, implying uncertainty in the result
States cannot be copied (“cloned”), implying that signal fanout is not permitted
Environmental interference can cause a measurement-like state collapse (decoherence) Quantum Circuit Characteristics

Classical vs. Quantum Circuits :

Classical vs. Quantum Circuits Classical adder

Classical vs. Quantum Circuits :

Classical vs. Quantum Circuits Quantum adder Here we use Pauli rotations notation.
Controlled σx is the same as controlled NOT Controlled σx is the same as Feynman Controlled-controlled σx is the same as Toffoli

Reversible Circuits :

Reversible Circuits

Reversible Circuits :

Reversible Circuits Reversibility was studied around 1980 motivated by power minimization considerations
Bennett, Toffoli et al. showed that any classical logic circuit C can be made reversible with modest overhead i Reversible Boolean
Circuit f(i) “Junk” i “Junk”

Reversible Circuits :

How to make a given f reversible
Suppose f :i f(i) has n inputs m outputs
Introduce n extra outputs and m extra inputs
Replace f by frev: i, j i, f(i) j where is XOR
Example 1: f(a,b) = AND(a,b)
This is the well-known Toffoli gate, which realizes AND when c = 0, and NAND when c = 1. Reversible Circuits

Reversible Circuits :

Reversible gate family [Toffoli 1980] Reversible Circuits Every Boolean function has a reversible implementation using Toffoli gates.
There is no universal reversible gate with fewer thanthree inputs

Quantum Gates :

Quantum Gates

Quantum Gates :

Quantum Gates One-Input gate: NOT
Input state: c0|0 + c1|1
Output state: c1|0 + c0|1
Pure states are mapped thus: |0 |1 and |1 |0
Gate operator (matrix) is
As expected:

Quantum Gates :

Quantum Gates One-Input gate: “Square root of NOT”
Some matrix elements are imaginary
Gate operator (matrix):
We find:
so |0 |0 with probability |i/2|2 = 1/2
and |0 |1 with probability |1/ 2|2 = 1/2
Similarly, this gate randomizes input |1
But concatenation of two gates eliminates the randomness!

Slide 54:

Other variant of square root of not - we do not use complex numbers - only real numbers

Universal One-Input Gate Sets
Requirement:
Hadamard and phase-shift gates form a universal gate set of 1-qubit gates, every 1-qubit gate can be built from them.
Example: The following circuit generates |y = cos |0 + ei sin |1 up to a global factor Quantum Gates

Slide 57:

Other Quantum Gates

Quantum Gates :

Two-Input Gate: Controlled NOT (CNOT) Quantum Gates CNOT maps |x|0 |x||x and |x|1 |x||NOT x
|x|0 |x||x looks like cloning, but it’s not. These mappings are valid only for the pure states |0 and |1
Serves as a “non-demolition” measurement gate

Slide 59:

Polarizing Beam-Splitter CNOT gate from [Cerf,Adami, Kwiat]

General controlled gates that control some 1-qubit unitary operation U are useful Quantum Gates U C(U) U C2(U) U U etc.

Quantum Gates :

Universal Gate Sets
To implement any unitary operation on n qubits exactly requires an infinite number of gate types
The (infinite) set of all 2-input gates is universal
Any n-qubit unitary operation can be implemented using (n34n) gates [Reck et al. 1994]
CNOT and the (infinite) set of all 1-qubit gates is universal Quantum Gates

Quantum Gates :

Discrete Universal Gate Sets
The error on implementing U by V is defined as
If U can be implemented by K gates, we can simulate U with a total error less than with a gate overhead that is polynomial in log(K/)
A discrete set of gate types G is universal, if we can approximate any U to within any > 0 using a sequence of gates from G Quantum Gates

Quantum Gates :

Discrete Universal Gate Set
Example 1: Four-member “standard” gate set Quantum Gates CNOT Hadamard Phase /8 (T) gate Example 2: {CNOT, Hadamard, Phase, Toffoli}

:

Quantum Circuits

Quantum Circuits :

A quantum (combinational) circuit is a sequence of quantum gates, linked by “wires”
The circuit has fixed “width” corresponding to the number of qubits being processed
Logic design (classical and quantum) attempts to find circuit structures for needed operations that are
Functionally correct
Independent of physical technology
Low-cost, e.g., use the minimum number of qubits or gates
Quantum logic design is not well developed! Quantum Circuits

Quantum Circuits :

Ad hoc designs known for many specific functions and gates
Example 1 illustrating a theorem by [Barenco et al. 1995]: Any C2(U) gate can be built from CNOTs, C(V), and C(V†) gates, where V2 = U Quantum Circuits (1+i) (1-i)
(1-i) (1+i) 1/2 (1-i) (1+i)
(1+i) (1-i) 1/2

Quantum Circuits |1
|1
|x |1
|1
V|x |1
|0 |1
|0
V|x |1
|1 |1
|1
U|x Example 1: Simulation (contd.) ? Exercise: Simulate the two remaining cases

Quantum Circuits :

Quantum Circuits Example 1: Algebraic analysis Is U0(x1, x2, x3) = U5U4U3U2U1(x1, x2, x3)
= (x1, x2, x1x2 U (x3) ) ? We will verify unitary matrix of Toffoli gate Observe that the order of matrices Ui is inverted.

Quantum Circuits :

Quantum Circuits Example 1 (contd); Kronecker since this is a parallel connection Unitary matrix of a wire Unitary matrix of a controlled V gate (from definition) We calculate the Unitary Matrix U1 of the first block from left.

Quantum Circuits :

Quantum Circuits Example 1 (contd); We calculate the Unitary Matrix U2 of the second block from left. Unitary matrix of CNOT or Feynman gate with EXOR down As we can check in the schematics, the Unitary Matrices U2 and U4 are the same

Quantum Circuits :

Quantum Circuits Example 1 (contd);

Quantum Circuits :

Quantum Circuits Example 1 (contd);
U5 is the same as U1 but has x1and x2 permuted (tricky!)
It remains to evaluate the product of five 8 x 8 matrices U5U4U3U2U1 using the fact that VV† = I and VV = U

Quantum Circuits :

Quantum Circuits Example 1 (contd);
We calculate matrix U3 This is a hermitian matrix, so we transpose and next calculate complex conjugates, we denote complex conjugates by bold symbols 1 0
0 1 1 0 0 0
0 1 0 0
0 0 v00 v10
0 0 v01 v11 =

Quantum Circuits :

Quantum Circuits Example 1 (contd);
U5 is the same as U1 but has x1and x2 permuted because in U1 black dot is in variable x2 and in U5 black dot is in variable x1
This can be also checked by definition, see next slide. U5 =

Quantum Circuits :

Quantum Circuits Example 1 (here we explain in detail how to calculate U5) . U5 x1 x2 x3 V U1 . U6 U6 U6 is calculated as a Kronecker product of U7 and I1
U7 is a unitary matrix of a swap gate U5 = U6 U 1 U 6

Quantum Circuits :

Quantum Circuits Example 1 (contd);
It remains to evaluate the product of five 8 x 8 matrices U5U4U3U2U1 using the fact that VV† = I and VV = U U1

Slide 79:

Quantum Circuits Implementing a Half Adder
Problem: Implement the classical functions sum = x1 x0 and carry = x1x0
Generic design: |x1 Uadd |x0 |y1 |y0 |x1 |x0 |y1 carry |y0 sum

Quantum Circuits Half Adder: Specific (reduced) design |x1 |x0 |y |x1 |y carry sum C2NOT (Toffoli) CNOT

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.