Introduction to Quantum Computing: Exploring the Future of Information Processing

 
Quantum computing
 
 
COMP308 Lecture notes based on:
 
Introduction to Quantum Computing
http://www.cs.uwaterloo.ca/~cleve/CS497-F07
Richard Cleve, Institute for Quantum Computing, University of Waterloo
 
Introduction to Quantum Computing and Quantum Information Theory
Dan C. Marinescu and Gabriela M. Marinescu
Computer Science Department , University of Central Florida
2
Moore’s Law
Moore’s Law
 
Measuring a state (e.g. position) disturbs it
Quantum systems sometimes seem to behave as if
they are in several states at once
Different evolutions can interfere with each other
 
Following trend … atomic scale in 15-20 years
 
Quantum mechanical effects occur at this scale:
3
Quantum mechanical effects
Quantum mechanical effects
Additional nuisances to overcome?
or
New types of behavior to make use of?
 
[Shor ’94]: polynomial-time algorithm for factoring integers on a 
quantum computer
 
This could be used to break most of the existing public-key cryptosystems, including
RSA, and elliptic curve crypto
 
[Bennett, Brassard ’84]: provably secure codes with short keys
4
Also with quantum information:
Also with quantum information:
 
Fast
er
 algorithms for combinatorial search problems
Fast algorithms for simulating quantum mechanics
Communication savings in distributed systems
More efficient notions of “proof systems”
 
Quantum information theory
 is a
generalization of the 
classical information
theory
 that we all know—which is based on
probability theory
 
What is a quantum computer?
 
  A quantum computer is a machine that performs
calculations based on the laws of quantum mechanics,
which is the behavior of particles at the sub-atomic level.
 
 
Introduction
 
 “I think I can safely say that nobody understands quantum
mechanics” - Feynman
 1982 - Feynman proposed the idea of creating machines based
on the laws of quantum mechanics instead of the laws of
classical physics.
 
 1985 - David Deutsch developed the quantum turing machine,
showing that quantum circuits are universal.
 1994 - Peter Shor came up with a quantum algorithm to factor very
large numbers in polynomial time.
1997 - Lov Grover develops a quantum search algorithm with O(√N)
complexity
 
Representation of Data  - Qubits
 
A bit of data is represented by a single atom that is in one of two states denoted
by 
|0>
 and 
|1>
.  A single bit of this form is known as a 
qubit
A physical implementation of a qubit could use the two energy levels of an atom.
An excited state representing |1> and a ground state representing |0>.
 
Excited
State
 
Ground
State
 
Nucleus
 
Light pulse of
frequency 
 
for
time interval t
 
Electron
 
State |0>
 
State |1>
 
Representation of Data - 
Superposition
 
A single qubit can be forced into a 
superposition
 of the two states denoted by the
addition of the state vectors:
 
|
> = 
  
|0> + 
  |1>
 
Where 
   and 
   
are complex numbers and 
|
  |   +  | 
  |   = 1
A qubit in superposition is in both of the states |1> and |0 at the same time
 
Representation of Data - Superposition
 
Light pulse of
frequency 
 for time
interval t/2
 
State |0>
 
State |0> + |1>
 
Consider a 3 bit qubit register.  An equally weighted
superposition of all possible states would be denoted by:
|
> =     
|000> + 
 
   |001> + . . . +     |111>
 
One qubit
 
Mathematical abstraction
Vector in a two dimensional complex vector space
(Hilbert space)
Dirac’s notation
ket 
                   column vector
bra 
                   row vector
 
 
bra 
 dual vector (transpose and complex
conjugate)
 
11
 
A bit versus a qubit
 
A bit
Can be in two distinct states, 0 and 1
A measurement does not affect the state
A qubit
can be in state           or in state      or in any other state
that is a linear combination of the basis state
When we measure the qubit we find it
in state           with probability
in state           with probability
 
are complex numbers
are complex numbers
 
The Boch sphere representation of one qubit
 
A 
qubit
 in a superposition state is represented as a
vector connecting the center of the Bloch sphere
with a point on its periphery.
The two probability amplitudes can be expressed
using Euler angles.
 
13
 
Qubit measurement
 
Two qubits
 
Represented as vectors in a 2-dimensional Hilbert
space with four basis vectors
 
When we measure a pair of qubits we decide that
the system it is in one of four states
 
 
with probabilities
 
15
 
Measuring two qubits
 
Before a measurement the state of the system
consisting of two qubits is uncertain (it is given by
the previous equation and the corresponding
probabilities).
After the measurement the state is certain, it is
   00, 01, 10, or 11 like in the case of a classical two bit
system.
 
16
 
Measuring two qubits (cont’d)
 
What if we observe only the first qubit, what
conclusions can we draw?
We expect that the system to be left in an uncertain
sate, because we did not measure the second qubit
that can still be in a continuum of states. The first
qubit can be
0 with probability
1 with probability
 
17
 
Bell state
 
1/sqrt(2) |0> + 1/sqrt(2) |1>
Measurement of a qubit in that state gives
50% of time logic 0, 50% of time logic.
Can also be denoted as |+>
 
18
 
Entanglement
 
Entanglement is an elegant, almost exact translation
of the German term Verschrankung used by
Schrodinger who was the first to recognize this
quantum effect.
An entangled pair is a single quantum system in a
superposition of equally possible states. The
entangled state contains no information about the
individual particles, only that they are in opposite
states.
The important property of an entangled pair is that
the measurement of one particle influences the state
of the other particle. Einstein called that “Spooky
action at a distance".
 
 
 
Due to the nature of quantum physics, the destruction of information in a gate
will cause heat to be evolved which can destroy the superposition of qubits.
 
Operations on Qubits - Reversible Logic
 
Input
 
Output
 
A
 
B
 
C
In these 3 cases,
information is being
destroyed
 
Ex.
The AND Gate
 
This type of gate cannot be used.  We must use 
Quantum Gates
.
 
Quantum Gates
 
  Quantum Gates are similar to classical gates, but do not have a degenerate
output. i.e. their original input state can be derived from their output state,
uniquely.  
They must be reversible.
This means that a deterministic computation can be performed on a quantum
computer only if it is reversible.  Luckily, it has been shown that any deterministic
computation can be made reversible.(Charles Bennet, 1973)
 
 
21
 
22
 
One qubit gates
 
I 
 identity gate; leaves a qubit unchanged.
 X or  NOT gate
 transposes the components
of an input qubit.
 Y gate.
 Z gate 
  flips the sign of a qubit.
 H 
 
the Hadamard gate.
 
Quantum Gates - Hadamard
 
Simplest gate involves one qubit and is called a 
Hadamard Gate (
also known as a
square-root of NOT gate.)  Used to put qubits into superposition.
 
H
 
State
|0>
 
State
|0> + |1>
 
H
 
State
|1>
Note:
 Two Hadamard gates used in
succession can be used as a NOT gate
 
Quantum Gates - Controlled NOT
 
 
 
A gate which operates on two qubits is called a 
Controlled-NOT (CN) Gate.  
If
the bit on the control line is 1, invert the bit on the target line.
 
A - Target
 
B - Control
 
Input
 
Output
Note:
 The CN gate has a similar behavior to the XOR gate with some
extra information to make it reversible.
 
A’
 
B’
Example Operation - Multiplication By 2
Carry Bit
Input
Output
Ones Bit
 We can build a reversible logic circuit to calculate multiplication by 2 using CN gates
arranged in the following manner:
0
 
Quantum Gates - Controlled Controlled NOT (CCN)
 
A - Target
 
B - Control 1
 
C - Control 2
 
Input
 
Output
 
A’
 
B’
 
C’
 
A gate which operates on three qubits is called a 
Controlled Controlled NOT
(CCN) Gate.  
Iff the bits on both of the control lines is 1,then the target bit is
inverted.
 
A Universal Quantum Computer
 
 The CCN gate has been shown to be a 
universal 
reversible logic gate as it can be
used as a NAND gate.
 
A - Target
 
B - Control 1
 
C - Control 2
 
Input
 
Output
 
A’
 
B’
 
C’
When our target input is 1, our target
output is a result of a NAND of B and C.
28
Classical and quantum systems
Classical and quantum systems
 
Probabilistic states:
 
Quantum states:
 
Dirac
 
notation: 
|
000
, 
|
001
, 
|
010
, …, 
|
111
 
are basis vectors,
so
29
Dirac bra/ket notation
Dirac bra/ket notation
Ket:
 
ψ
 
always denotes a column vector, e.g. 
 
Bra
c
ket
:
 
φ
ψ
 denotes 
φ
ψ
, the inner product of 
φ
 
and
 
ψ
 
Bra:
 
ψ
 
always denotes a row vector that is the conjugate transpose of 
ψ
, e.g.  
[
*
1
   
*
2 
  
   
*
d
 
]
 
Convention:
30
Basic operations on qubits (I)
Basic operations on qubits (I)
(0) Initialize qubit to 
|
0
 or to 
|
1
 
(1) Apply a 
unitary
 operation 
U
   
(
formally
 
U
U
 
=
 
I 
)
 
Examples:
31
Basic operations on qubits (II)
Basic operations on qubits (II)
Hadamard:
More examples of unitary operations: 
(unitary 
 
rotation)
0
1
32
Basic operations on qubits (III)
Basic operations on qubits (III)
(3) Apply a “standard” measurement:
 
 
(
) There exist 
other
 quantum operations, but they can all be “simulated” by
the aforementioned types
 
Example:
 measurement with respect to a different orthonormal basis 
{
ψ
0
, 
ψ
1
}
|
|
2
|
|
2
0
1
 
ψ
0
 
ψ
1
… and the quantum state collapses 
     
to 
0
 
or 
1
33
Distinguishing between two states
Distinguishing between two states
Question 1:
 can we distinguish between the two cases?
Let           be in state  
                                 
or 
 
 
Distinguishing procedure:
1.
apply 
H
2.
measure
 
This works because
  H
 
+
 
=
 
0
  
and
  
H
 
 
=
 
1
Question 2:
 can we distinguish between 
0
 and 
+
?
 
Since they’re not orthogonal, they 
cannot be perfectly
 
distinguished
 … but statistical
difference is detectable
34
Operations on 
Operations on 
n
n
-qubit states
-qubit states
 
… and the quantum state collapses
 
(
U
U
 = 
I
 
)
35
Entanglement
Entanglement
 
The state of the combined system their 
tensor product
:
 
??
 
Suppose that two qubits are in states:
 
Answers:      
1.
2.
 
... this is an 
entangled
 state
36
Structure among subsystems
Structure among subsystems
 
37
 
Quantum circuits
Quantum circuits
 
Computation is “feasible” if circuit-size scales polynomially
 
38
 
39
 
One qubit gates
 
40
 
Identity transformation, Pauli matrices, Hadamard
 
41
 
Tensor products and ``outer’’ products
 
42
 
CNOT a two qubit gate
 
Two inputs
Control
Target
 
The control qubit is transferred to the output as is.
The target qubit
Unaltered if the control qubit is 0
Flipped if the control qubit is 1.
 
43
 
44
 
The two input qubits of a two qubit gates
 
45
 
Two 
qubit
 gates
 
46
 
Two qubit gates
 
47
 
Final comments on the CNOT gate
 
CNOT preserves the control qubit  (the first and the
second component of the input vector are
replicated in the output vector) and flips the target
qubit (the third and fourth component of the input
vector become the fourth and respectively the
third component of the output vector).
 
 
The CNOT gate is reversible. The control qubit is
replicated at the output and knowing it we can
reconstruct the target input qubit.
48
Example of a one-qubit gate applied to a
Example of a one-qubit gate applied to a
two-qubit system
two-qubit system
Question:
 what happens if 
U
 is applied to the 
first
 qubit?
49
Controlled-
Controlled-
U
U
 gates
 gates
U
 
0

0
 
 
0

0
 
0

1
 
0

1
 
1

0
 
 
1
U
0
1

1
 
 
1
U
1
 
Maps basis states as:
 
Resulting 4x4 matrix is
controlled-
U 
=
50
Controlled-
Controlled-
NOT
NOT
 
 
(CNOT)
(CNOT)
 
Note:
 “control” qubit may change on some input states!
51
Multiplication problem
Multiplication problem
 
“Grade school” algorithm takes 
O
(
n
2
) 
steps
Best currently-known 
classical 
algorithm costs 
O
(
n
 
log
n 
loglog
 
n
)
Best currently-known 
quantum
 method: same
Input:
 two 
n
-bit numbers (e.g. 
101
 and 
111
)
Output:
 their product (e.g. 
100011
)
52
Factoring problem
Factoring problem
 
Trial division costs  
 
2
n
/
2
Best currently-known 
classical
 algorithm costs 
O
(
2
n
 
log
 
n
 
)
Hardness of factoring is the basis of the security of many
cryptosystems (e.g. RSA)
Shor’s 
quantum
 algorithm costs 
 
n
2
      [
 
O
(
n
2
 
log
 
n
 
loglog
 
n
)
 
]
Implementation would break RSA and other cryptosystems
Input:
 an 
n
-bit number (e.g. 
100011
)
Output:
 their product (e.g. 
101
,
 111
)
 
Grover’s Search Algorithm
 
• Search in a database with N names.
• Names are randomly entered.
• Classically on average N/2 search is required.
O(N) operations is required.
• Quantum computation requires O(sqrt(N))
operations
54
How do quantum algorithms work?
How do quantum algorithms work?
 
This is 
not 
performing “exponentially many computations at polynomial cost”
 
But we can make some interesting 
tradeoffs
:
instead of learning about any  
(
x
,
 
f
 
(
x
)
)  
point, one can learn something about a 
global
property
 of  
f
 
Given a polynomial-time classical algorithm for  
f
 
:{0
,
1}
n
 
 
T
, it is straightforward to
construct a quantum algorithm that creates the state:
 
The most straightforward way of extracting information from the state yields just
(
x
,
 
f
 
(
x
)
)
  for a random  
x
{0
,
1}
n
55
Deutsch’s problem
Deutsch’s problem
Let  
f 
: {0,1} 
 {0,1}
 
There are 
four
 possibilities:
 
Goal: 
determine  
f
(
0
) 
 
f
(
1
)
 
Any classical method requires 
two
 queries
 
What about a quantum method?
56
Reversible
Reversible
 black box for 
 black box for 
f
f
U
f
a
 
b
a
b
 
 
f
(
a
)
 
2
 queries + 
1
 auxiliary operation
57
Quantum algorithm for Deutsch
Quantum algorithm for Deutsch
H
H
H
1
0
f
(
0
) 
 
f
(
1
)
 
1 
query + 
4
 auxiliary operations
 
How does this algorithm work?
 
Each of the three 
H
 operations can be seen as playing a different role ...
58
Quantum algorithm (
Quantum algorithm (
1
1
)
)
 
1.
 Creates the state 
0
 
 
1
, which is an eigenvector of
1
2
3
 
This causes 
f  
to induce a 
phase shift
 of (
1
)
 
f
(
x
)
 to 
x
59
Quantum algorithm (
Quantum algorithm (
2
2
)
)
2.
 Causes  
f
  to be queried 
in superposition 
(at 
0
 
+
 
1
)
 
(
0
 
+
 
1
)
 
(
0
 
 
1
)
60
Quantum algorithm (
Quantum algorithm (
3
3
)
)
3.
 Distinguishes between  
(
0
 
+
 
1
)  
and  
(
0
 
 
1
)
 
61
 
Summary of  Deutsch’s algorithm
Summary of  Deutsch’s algorithm
constructs eigenvector so 
f
-queries
induce phases: 
x
 
 
(
1
)
 
f
(
x
)
x
produces superpositions of
inputs to 
f 
:  
0
 
+
 
1
extracts phase differences from
 
 
(
1
)
 
f
(
0
)
0
 
+
 
(
1
)
 
f
(
1
)
1
 
Makes only one query, whereas two are needed classically
62
One-out-of-four search
One-out-of-four search
Let  
f 
: {0,1}
2
 
 {0,1} 
have the property that there is exactly one 
x 
 
{0,1}
2 
 
for
which 
f
 
(
x
) 
=
 1
 
Four possibilities:
 
Goal: 
find 
x 
 
{0,1}
2 
 
for which 
f
 
(
x
) 
=
 1
 
What is the minimum number of queries 
classically?
 
____
 
Quantumly?
 ____
63
Quantum algorithm (I)
Quantum algorithm (I)
 
(
(
1
)
 
f
(
00
)
00
 
+
 
(
1
)
 
f
(
01
)
01
 
+ 
(
1
)
 
f
(
10
)
10
 
+
 
(
1
)
 
f
(
11
)
11
)(
0
 
 
1
)
 
Output
 state of query?
Black box for 1-4 search:
 
Start by creating phases in superposition of all inputs to 
f
:
 
Input 
state to query?
 
(
00
 
+
 
01
 
+ 
10
 
+
 
11
)(
0
 
 
1
)
64
Quantum algorithm (II)
Quantum algorithm (II)
Output state of the first two qubits in the four cases:
 
Case of 
f
00
?
 
ψ
01
 
=
 
+
  
00
 
 
01
 
+ 
10
 
+
 
11
 
ψ
10
 
=
 
+
  
00
 
+
 
01
 
 
10
 
+
 
11
 
ψ
11
 
=
 
+
  
00
 
+
 
01
 
+ 
10
 
 
11
 
What noteworthy property do these states have?      
  Orthogonal
 
ψ
00
 
=
 
  
00
 
+
 
01
 
+ 
10
 
+
 
11
 
Case of 
f
01
?
 
Case of 
f
10
?
 
Case of 
f
11
?
 
  
Apply the 
U
 that maps
  
ψ
00
,
 
ψ
01
,
 
ψ
10
,
 
ψ
11
  
to
  
00
,
 
01
,
 
10
,
 
11
 
 (resp.)
 
What makes a quantum algorithm potentially faster than
any classical one?
 
Quantum parallelism:
 by using superpositions of
quantum states, the computer is executing the
algorithm on all possible inputs at once
Dimension of quantum Hilbert space:
 the “size”
of the state space for the quantum system is
exponentially larger than the corresponding
classical system
 
Entanglement capability:
 different subsystems
(qubits) in a quantum computer become
entangled, exhibiting nonclassical correlations
 
Quantum algorithms research
 
Require more quantum algorithms in order to:
solve problems more efficiently
 understand the power of quantum computation
 make valid/realistic assumptions for information
security
 Problems for quantum algorithms research:
requires close collaboration between physicists and
computer scientists
highly non-intuitive nature of quantum physics
even classical algorithms research is difficult
 
Summary of quantum algorithms
 
It may be possible to solve a problem on a quantum system
 much faster (i.e., using fewer steps) than on a classical
computer
 Factorization and searching are examples of problems
where quantum algorithms are known and are faster than
any classical ones
 Implications for cryptography, information security
 Study of quantum algorithms and quantum computation is
important in order to make assumptions about adversary’s
algorithmic and computational capabilities
 Leading to an understanding of the computational power
of quantum vs classical systems
 
Conclusion
 
  In 2001, a 7 qubit machine was built and programmed to
run Shor’s algorithm to successfully factor 15.
 What algorithms will be discovered next?
Can quantum computers solve NP Complete problems in
polynomial time?
Slide Note
Embed
Share

Quantum computing revolutionizes information processing by leveraging quantum mechanics principles, enabling faster algorithms and secure code systems. Advancements in quantum information theory promise efficient distributed systems and combinatorial problem-solving. Discover the evolution of quantum computing, key milestones, and potential applications in this cutting-edge field.


Uploaded on Jul 16, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Quantum computing COMP308 Lecture notes based on: Introduction to Quantum Computing http://www.cs.uwaterloo.ca/~cleve/CS497-F07 Richard Cleve, Institute for Quantum Computing, University of Waterloo Introduction to Quantum Computing and Quantum Information Theory Dan C. Marinescu and Gabriela M. Marinescu Computer Science Department , University of Central Florida

  2. Moores Law number of transistors 109 108 107 106 105 year 104 1975 1980 1985 1990 1995 2000 2005 Following trend atomic scale in 15-20 years Quantum mechanical effects occur at this scale: Measuring a state (e.g. position) disturbs it Quantum systems sometimes seem to behave as if they are in several states at once Different evolutions can interfere with each other 2

  3. Quantum mechanical effects Additional nuisances to overcome? or New types of behavior to make use of? [Shor 94]: polynomial-time algorithm for factoring integers on a quantum computer This could be used to break most of the existing public-key cryptosystems, including RSA, and elliptic curve crypto [Bennett, Brassard 84]: provably secure codes with short keys 3

  4. Also with quantum information: Faster algorithms for combinatorial search problems Fast algorithms for simulating quantum mechanics Communication savings in distributed systems More efficient notions of proof systems quantum information theory Quantum information theory is a generalization of the classical information theory that we all know which is based on probability theory classical information theory 4

  5. What is a quantum computer? A quantum computer is a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the sub-atomic level.

  6. Introduction I think I can safely say that nobody understands quantum mechanics - Feynman 1982 - Feynman proposed the idea of creating machines based on the laws of quantum mechanics instead of the laws of classical physics. 1985 - David Deutsch developed the quantum turing machine, showing that quantum circuits are universal. 1994 - Peter Shor came up with a quantum algorithm to factor very large numbers in polynomial time. 1997 - Lov Grover develops a quantum search algorithm with O( N) complexity

  7. Representation of Data - Qubits A bit of data is represented by a single atom that is in one of two states denoted by |0> and |1>. A single bit of this form is known as a qubit A physical implementation of a qubit could use the two energy levels of an atom. An excited state representing |1> and a ground state representing |0>. Light pulse of frequency for time interval t Excited State Nucleus Ground State Electron State |0> State |1>

  8. Representation of Data - Superposition A single qubit can be forced into a superposition of the two states denoted by the addition of the state vectors: | > = |0> + |1> 1 2 2 2 Where and are complex numbers and | | + | | = 1 1 2 1 2 A qubit in superposition is in both of the states |1> and |0 at the same time

  9. Representation of Data - Superposition Light pulse of frequency for time interval t/2 State |0> State |0> + |1> Consider a 3 bit qubit register. An equally weighted superposition of all possible states would be denoted by: 1 1 1 | > = |000> + |001> + . . . + |111> 8 8 8

  10. One qubit Mathematical abstraction Vector in a two dimensional complex vector space (Hilbert space) Dirac s notation ket column vector bra row vector | bra dual vector (transpose and complex conjugate)

  11. = + 0 1 0 | 1 A bit versus a qubit 0 | , are complex numbers 1 + = 2 2 | | | | 1 0 1 A bit Can be in two distinct states, 0 and 1 A measurement does not affect the state A qubit can be in state or in state or in any other state that is a linear combination of the basis state When we measure the qubit we find it in state with probability in state with probability 1 | = + 0 1 0 1 0 | 1 | | | 2 0 | 0| 1| 2 11

  12. The Boch sphere representation of one qubit A qubit in a superposition state is represented as a vector connecting the center of the Bloch sphere with a point on its periphery. The two probability amplitudes can be expressed using Euler angles. | 0 > z | r y b x | 1 >

  13. Qubit measurement 0 p0 0 0 Basis (logical) state 0 Superposition states p1 Basis (logical) state 1 1 1 (a) One bit (b) One qubit 1 Possible states of one qubit before the measurement The state of the qubit after the measurement 13

  14. Two qubits Represented as vectors in a 2-dimensional Hilbert space with four basis vectors 10 , 01 , 00 , 11 When we measure a pair of qubits we decide that the system it is in one of four states , 01 , 00 10 , 11 2 2 2 2 | | , | | , | | , | | with probabilities 00 01 10 11 00 01 10 11 = + + + 00 01 10 11 00 01 10 11 + + + = | | | | | | | | 1 2 2 2 2

  15. Measuring two qubits Before a measurement the state of the system consisting of two qubits is uncertain (it is given by the previous equation and the corresponding probabilities). After the measurement the state is certain, it is 00, 01, 10, or 11 like in the case of a classical two bit system. 15

  16. Measuring two qubits (contd) What if we observe only the first qubit, what conclusions can we draw? We expect that the system to be left in an uncertain sate, because we did not measure the second qubit that can still be in a continuum of states. The first qubit can be 0 with probability 1 with probability 10 | | + + 2 2 | | | | 00 01 2 2 | | 11 16

  17. Bell state 1/sqrt(2) |0> + 1/sqrt(2) |1> Measurement of a qubit in that state gives 50% of time logic 0, 50% of time logic. Can also be denoted as |+> 17

  18. Entanglement Entanglement is an elegant, almost exact translation of the German term Verschrankung used by Schrodinger who was the first to recognize this quantum effect. An entangled pair is a single quantum system in a superposition of equally possible states. The entangled state contains no information about the individual particles, only that they are in opposite states. The important property of an entangled pair is that the measurement of one particle influences the state of the other particle. Einstein called that Spooky action at a distance". 18

  19. Operations on Qubits - Reversible Logic Due to the nature of quantum physics, the destruction of information in a gate will cause heat to be evolved which can destroy the superposition of qubits. Ex. Input Output In these 3 cases, information is being destroyed The AND Gate A B C 0 0 0 A 0 1 0 C 1 0 0 B 1 1 1 This type of gate cannot be used. We must use Quantum Gates.

  20. Quantum Gates Quantum Gates are similar to classical gates, but do not have a degenerate output. i.e. their original input state can be derived from their output state, uniquely. They must be reversible. This means that a deterministic computation can be performed on a quantum computer only if it is reversible. Luckily, it has been shown that any deterministic computation can be made reversible.(Charles Bennet, 1973)

  21. = + = + ' ' 0 1 0 1 0 1 0 1 One-qubit gate = 21 g g g 11 12 G g 22 0 g g = G 11 12 0 = 1 g g 21 22 1 21

  22. One qubit gates I identity gate; leaves a qubit unchanged. X or NOT gate transposes the components of an input qubit. Y gate. Z gate flips the sign of a qubit. H the Hadamard gate. 22

  23. Quantum Gates - Hadamard Simplest gate involves one qubit and is called a Hadamard Gate (also known as a square-root of NOT gate.) Used to put qubits into superposition. H H State |1> State |0> State |0> + |1> Note: Two Hadamard gates used in succession can be used as a NOT gate

  24. Quantum Gates - Controlled NOT A gate which operates on two qubits is called a Controlled-NOT (CN) Gate. If the bit on the control line is 1, invert the bit on the target line. Input Output A B A B A A - Target 0 0 0 0 0 1 1 1 B B - Control 1 0 1 0 1 1 0 1 Note: The CN gate has a similar behavior to the XOR gate with some extra information to make it reversible.

  25. Example Operation - Multiplication By 2 We can build a reversible logic circuit to calculate multiplication by 2 using CN gates arranged in the following manner: Input Output Carry Bit Ones Bit Carry Bit Ones Bit 0 0 0 0 0 1 1 0 0 Carry Bit Ones Bit H

  26. Quantum Gates - Controlled Controlled NOT (CCN) A gate which operates on three qubits is called a Controlled Controlled NOT (CCN) Gate. Iff the bits on both of the control lines is 1,then the target bit is inverted. Output Input A B C A B C 0 0 0 0 0 0 A A - Target 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 B B - Control 1 1 0 0 1 0 0 1 0 1 1 0 1 C C - Control 2 1 1 0 1 1 0 1 1 1 0 1 1

  27. A Universal Quantum Computer The CCN gate has been shown to be a universal reversible logic gate as it can be used as a NAND gate. Output Input A A - Target A B C A B C 0 0 0 0 0 0 0 0 1 0 0 1 B B - Control 1 0 1 0 0 1 0 0 1 1 1 1 1 C 1 0 0 1 0 0 C - Control 2 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 When our target input is 1, our target output is a result of a NAND of B and C.

  28. Classical and quantum systems 000 p Probabilistic states: Quantum states: 000 001 p 001 , x x, 0 x C x p 010 p 010 011 p x x 2= = 1 1 x x p 011 100 p 100 101 p 101 110 p 110 111 p 111 Diracnotation: |000 , |001 , |010 , , |111 are basis vectors, x so = xx 28

  29. Dirac bra/ket notation Ket: always denotes a column vector, e.g. 1 2 1 0 = = 0 1 Convention: 0 1 d Bra: always denotes a row vector that is the conjugate transpose of , e.g. [ *1 *2 *d] Bracket: denotes , the inner product of and 29

  30. Basic operations on qubits (I) 0 1 (0) Initialize qubit to |0 or to |1 = Recall = 1 0 1 0 (1) Apply a unitary operation U(formallyU U=I ) conjugate transpose Examples: cos sin Rotation by : sin cos 0 1 Maps |0 |1 |1 |0 = = X NOT (bit flip): x 1 0 1 0 Maps |0 |0 |1 |1 = = Z Phase flip: z 0 1 30

  31. Basic operations on qubits (II) 1 More examples of unitary operations: (unitary rotation) H 0 Reflection about this line 1 1 1 0 = Hadamard: H 1 1 2 H 1 + 1 ( ) 1 1 = + = 0 0 1 H + 1 2 2 + 1 ( ) 1 1 = = 0 1 H 1 1 2 2 31

  32. Basic operations on qubits (III) 1 1 (3) Apply a standard measurement: 2 0 with prob 0 | |2 0 + 1 2 1 with prob 0 | |2 and the quantum state collapses to 0 or 1 ( ) There exist otherquantum operations, but they can all be simulated by the aforementioned types Example: measurement with respect to a different orthonormal basis { 0 , 1 } 32

  33. Distinguishing between two states ( ) 1 ( ) 1 + = + 0 1 = Let be in state or 0 1 2 2 Question 1: can we distinguish between the two cases? Distinguishing procedure: 1. apply H 2. measure This works because H + = 0 and H = 1 Question 2: can we distinguish between 0 and + ? Since they re not orthogonal, they cannot be perfectlydistinguished but statistical difference is detectable 33

  34. Operations on n-qubit states U x x x Unitary operations: (U U = I ) x x x 000 001 Measurements: 2 000 with prob 111 000 2 001 with prob x xx 001 2 111 with prob 111 and the quantum state collapses 34

  35. Entanglement + + 0 1 ' 0 ' 1 Suppose that two qubits are in states: The state of the combined system their tensor product: ( )( ) + + = + + + 0 1 ' 0 ' 1 ' 00 ' 01 ' 10 ' 11 Question: what are the states of the individual qubits for ? + 00 01 10 11 1 1 1 1 1. 2 2 2 2 2. ? 11 + 00 1 1 2 2 ( )( ) + 0 1 0 1 1 1 1 1 Answers: 1. 2 2 2 2 2. ?? ... this is an entangled state 35

  36. Structure among subsystems qubits: time U #1 W #2 V #3 #4 unitary operations measurements 36

  37. Quantum circuits 0 1 1 0 1 1 0 0 1 1 0 1 Computation is feasible if circuit-size scales polynomially 37

  38. = + = + ' ' 0 1 0 1 0 1 0 1 One-qubit gate = 21 g g g 11 12 G g 22 0 g g = G 11 12 0 = 1 g g 21 22 1 38

  39. One qubit gates * 11 * 21 g g g g g g + = 11 12 = G G 11 21 = GT * 12 * 22 g g g g g g 21 22 12 22 + + * 11 * 21 * 11 * 21 g g g g g g g g + = = 11 21 12 22 G G I + + * 12 * 22 * 12 * 22 g g g g g g g g 11 21 12 22 39

  40. Identity transformation, Pauli matrices, Hadamard 1 0 = + 0 1 = = I 0 1 0 0 1 = + 0 1 0 1 1 0 = = X 1 1 0 = i + i 0 1 0 0 i i 1 0 = = Y 2 = 0 1 1 0 0 1 = = Z 3 0 1 + 0 1 0 1 = + 1 1 1 = H 0 1 2 2 1 1 2 40

  41. Tensor products and ``outer products 1 1 1 0 = = = 00 0 | 0 | 0 0 0 0 1 1 0 0 0 0 0 0 0 0 ( ) = = 00 00 1 0 0 0 0 0 0 0 0 0 0 0 0 0 41

  42. CNOT a two qubit gate Control input Two inputs Control Target Target input O + + O addition modulo 2 The control qubit is transferred to the output as is. The target qubit Unaltered if the control qubit is 0 Flipped if the control qubit is 1. 42

  43. = = CNOT V W CNOT G CNOT V CNOT CNOT 1 0 0 0 0 1 0 0 = CNOT G 0 0 0 1 0 0 1 0 43

  44. The two input qubits of a two qubit gates = = + + 0 0 1 0 1 1 0 1 0 0 0 0 0 1 = = = CNOT V 1 1 1 0 1 1 44

  45. Two qubit gates = + + + 00 00 01 01 10 11 11 10 CNOT G 1 0 0 0 0 1 0 0 = CNOT G 0 0 0 1 0 0 1 0 45

  46. Two qubit gates = W CNOT G CNOT V CNOT 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 = = W CNOT 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 = + + + 00 01 10 11 W 0 0 0 1 1 1 1 0 CNOT = + + + 0 ( 0 1 ) 1 ( 0 1 ) W 0 0 1 1 1 0 CNOT 46

  47. Final comments on the CNOT gate CNOT preserves the control qubit (the first and the second component of the input vector are replicated in the output vector) and flips the target qubit (the third and fourth component of the input vector become the fourth and respectively the third component of the output vector). = + + + 0 ( 0 01 ) 1 ( 0 1 ) W 0 0 1 1 1 0 CNOT The CNOT gate is reversible. The control qubit is replicated at the output and knowing it we can reconstruct the target input qubit. 47

  48. Example of a one-qubit gate applied to a two-qubit system (do nothing) u u 00 01 = U u u 10 11 U The resulting 4x4 matrix is Maps basis states as: 0 0 u u 00 01 0 0 0 U 0 0 1 0 U 1 1 0 1 U 0 1 1 1 U 1 0 0 u u 10 0 11 0 = I U u u 00 01 0 0 u u 10 11 Question: what happens if U is applied to the first qubit? 48

  49. Controlled-U gates u u 00 01 = U u u 10 11 U Resulting 4x4 matrix is controlled-U = 1 0 0 0 Maps basis states as: 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 U 0 1 1 1 U 1 0 0 u u 00 01 0 0 u u 10 11 49

  50. Controlled-NOT(CNOT) a a a b b X Note: control qubit may change on some input states! H H 0 + 1 0 1 0 1 0 1 H H 50

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#