Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Quantum Computing

Building Blocks, Cryptography and Quantum Algorithms

Study Approach

Approach &Intro

Nature and the way things are

Why QC?

Applications

  • Increasing the number of transistors increases the computational power of the classical computer.
  • Implementing more transistors inside the integrated circuit is followed by smaller transistors and thinner gaps

Limitations

of classical

computers

  • extremely thin gates cause electrons to tunnel through the barrier in a phenomenon called quantum tunneling

Moore's Law:

  • The number of transistors that could fit in one integrated circuit would double about every two years.

To successfully simulate the quantum world we need to use a machine that obeys the quantum laws of physics.

  • Problems described by models to find optimal solutions such as: quantum chemistry, fluid mechanics, superconducting materials.

Simulations

  • Simulations dealing with pharmaceuticals, molecular simulations: model the behaviour of antibodies.

Rapid Feedback

Learning a larger number of concurrent patterns decreasing the time needed when learning it by a sequential approach

Machine

Learning

Quantum Computers

CAN

Cryptography

Break the “unbreakable” classical ciphers with seconds.

Generate “unbreakable” quantum ciphers.

Computers

Quantum

Classical

Quantum Particles

Electric Signal

How is QC

Different?

Quantum Gates

Transistors/Digital Circuits

Probablistic

Deterministic

Magic Behind Quantum Computing

  • Quantum computing exploits the weirdness of quantum mechanics.

Magic

Behind QC

  • See the big picture and put the pieces together to combine the knowledge of the quantum phenomena in making a quantum computer

basic unit

of information in a quantum computer

Data registeries: every qubit holds only 1 registry of information

Qubits

Atomic or subatomic particle

A unit vector in a two-dimensional complex vector space defined with a fixed orthonormal basis.

& are complex and represent the square root of the probability of the states

Mathematical Representation

Orthonormality

qubits are in superposition of &

  • Qubit has infinite possibilities of superpositions
  • One value is extracted when measuring the qubit
  • 0 & 1 are expressions holding many meanings depending on the system

Superposition

represent vector states visually

Any vector is represented by the two angles and on the surface of the sphere

In general

Bloch

Sphere

Number of basis vectors:

, where b is the number of basis vectors in a single qubit, and n is the number of qubits in the system.

Multi-Qubit

System

Basis vectors

We use tensor product which gives us all the possible values for the states of the qubits in the system.

2-Qubit

System

Basis vectors

the basis vectors are:

n=3

Basis vectors

n-Qubit

System

the minimum number of real numbers required to fully describe the state of that system

Degrees of

Freedom

We have 4 number: a,b,c,d

From orthonormality:

Single Qubit

System

Non physical sate representatoin uniqueness:

We have 2 constraints

DOF: 4-2=2

Classically

Combine 2 systems

New System

DOF-System1=2

DOF-NewSytem=2+2=4

DOF-System2=2

Qubits

n-Qubit

System

4 complex numbers: 8 real numbers

2 constraints

DOF: 8-2=6 > 4 ?

spooky action at a distance

Two quantum systems connected to each other, then any measurement on one system affects the other system instantly even if they were separated light years distances.

The states of these two qubits are shared and dependent on each other which adds more degrees of freedom

Entanglement

Bell State:

Probability of qubit 1 being measured 0, and qubit 2 being measured 0: 0.5

Probability of qubit 1 being measured 0, and qubit 2 being measured 1: 0

Probability of qubit 1 being measured 1, and qubit 2 being measured 0: 0

Probability of qubit 1 being measured 0, and qubit 2 being measured 0: 0.5

Probability of the qubits being measured with same values: 0.5 + 0.5 = 1

Probability of the qubits being measured with different values: 0 + 0 = 0

Mathematically

the probability of the first qubit being measured 0 is 0.5, but the probability of the second qubit being measured 0 is either 0 or 1 and it totally depends on the first measurement.

Test For Entanglement (Entanglement Criteria):

If a state vector of a multi-qubit system can be expressed as a tensor product of single-qubit states, then it is not entangled.

i.e

A B is always unentangled!

Test of Entanglement

Find such that:

A contracidction

A pair of photons in the Bell State

EPR

what Alice does with her particle affects Bob's measurement on his particle

what Bob does with his particle affects Alices's measurement on her particle

There is some hidden state which we cannot detect and this hidden state is local to each particle. The behavior of the entangled pair is determined by these hidden local states.

EPR Prediction

No local state can predict the results of an experiment and state has to be shared.

Bell's Theorem

Measurement

The probability of the qubit (S) being measured in alignment with an apparatus (A):

Measurement

The magnetic property of electrons

Spin is measured to be up or down

The initial spin of the electron??

Electron Spin

P

st

1 measurement

nd

2 measurement

Experiments

rd

3 measurement

P(aligned)

P(anti-aligned)

electromagnetic wave

The electric and magnetic oscillations are at right-angles to the direction of propagation of the wave

Each photon that is directed along the z-axis has its own angle, which is called the angle of polarization

Photon Polarization

plastic filter of light polarization.

Polarizing sheet:

Complete Measurement

P(00) =

P(10) =

P(11) =

P(01) = 0

Partial Measurement

We measure only one of the qubits

Parital

Measurements

If qubit 1

P(0) =

:

P(0) =

:

1- Measurement changes the state of the system.

2-Measurements cause the superposition to collapse.

3- The first measurement might be probabilistic.

4- The first measurement changes the state of the qubit so that subsequent measurements are deterministic.

Observatios

5- If the apparatus used is aligned with the qubit’s state, then the result is deterministic.

6- Random behaviour appears only when we measure the state in a direction that is not aligned (or anti-aligned) with the state.

7- The randomness caused by measurement is irreversible.

8- When partially measuring a system, all the system is affected and inconsistent states in the superposition disappear.

Quantum Circuits

Quantum gate is any operation that changes the state of the qubit.

Physically

Microwave pulses carefully calibrated and in resonance with the qubit’s transition frequency

Quantum

Circuits

Mathematically

Reversible matrix transformations .

Unitary Matrix:

No-Cloning Theorem:

Unkown systems cannot cloned.

entangled qubits have a shared state

Real-World

Circuits

Quantum Cryptography

Cryptography

Charles Bennett and Gilles Brassard in 1984

Single Use Shared-Secret

  • Random sequence of bytes
  • Single use
  • Non-random patterns reveals the secret.

Securing the Single Use Shared-Secret

BB84 Protocol

Vertically polarized photon

Bit: 1

Horizontally polarized photon

Bit: 2

Quantum Channel

Scenario 1

Bob

Alice

Aligned

Anti-aligned

Eve

Scenario 2

Cryptography with entanglement

  • Alice creates an EPR pair
  • Alice sends only one qubit to Bob
  • The pair is still entangled

Eckert Protocol

  • Alice measures her qubits in the direction of two different bases: Standard & Hadamard

P(Alice measuring 1 & Bob measuring 1 ) = 1

P(Alice measuring + & Bob measuring +) = 1

P(Alice measuring 1 & Bob measuring +) = 1/2

P(Alice measuring + & Bob measuring 1) = 1/2

  • Alice & Bob measure along bases randomly then check for wrong guesses
  • Eve is caught by probability checksum

Hadamard Basis

Mathematical trick to encode 2 bits of information onto a single qubit.

CNOT

4 Possibiliets:

Dense Coding

To Bob

Hadamard

The process of transferring an unknown state of a qubit to another qubit

No qubits are transferred, Alice only sends information.

Quantum

Teleportation

Alice Partailly measures her qubits.

result

Bob

Quantum Parallelism

Ability to be in superposition

n

Quantum

Algorithms

H generates a superposition of all 2 possible combinations of the inputs

n

2 function values f(x) along with their corresponding input value x in one cycle

First Algorithm By David Deutsch in 1985

If a function determine whether is constant or balanced.

constant

balanced

Deutsch's

Algorithm

:

Multiple bit generalization for Deutsch's problem

:

for

i=1:

00

0

Classically:

01

i=2:

0

i=3:

10

?

Quantum:

Deutsch's-

Jozsa

Algorithm

designed by Peter Shor in 1994 to solve the

integer factorization problem

The fundamental theorem of arithmetic

Every positive integer greater than one can be written uniquely as a product of primes

Used in Most protected Protocols (RSA): HTTPS, SSL ...

Shor's Algorithm

Quantum Algorithm for Period Finding

STEP-1: Initialize both registers to

STEP-2: Apply QFT on the first register :

M

STEP-3: Apply the modular exponentiation function U :

f (x)

a, N

STEP-4: Paritally measure the second register

The first register:

-1

STEP-5: Apply (QFT ) on the first register:

M

Superposition states with period , with no offset.

Quantum

Approach

A random multiple of

STEP-6: Measure the first register :

gcd(k, ,M)=

Whenever gcd(k, )=1

takes an M-dimensional complex vector to another M-dimensional complex vector with modified amplitude.

Quantum Fourier Transform

th

the n roots of unity are the complex solutions of the equation: .

Phase Estimation

Applying Wlash Transformation:

Modular Exponentiation

Classical Algorithm for integer factorization

STEP-1: Pick any integer a < N

STEP-2:

A- If a is not relatively prime to N. Then a is a common factor of N, a=p or a=q. #DONE

B- If a is relatively prime to N, that is gcd(a.N)=1. Then proceed to Step-3.

x

Step-3: Compute the period r of f (x) = a mod(N).

a,N

STEP-4: If r is odd, go back to STEP-1. If r is even, proceed to STEP-5.

Classical

Approach

r/2

STEP-5: If a + 1 = 0 mod(N), go back to STEP-1. Otherwise, proceed

to STEP-6.

r

STEP-6: a=1 mod(N), so a - 1 = 0 mod(N). Then, there exists a natural

number k, such that: a - 1 = k.N, where r is even.

r

r/2

So, (a - 1 )(a + 1) = k.N = k.p.q

r/2

STEP-7: Let p = gcd ((a - 1), N), and q= gcd((a + 1), N). #DONE

STEP-3

Integer Factorization

Period Finding

r

Least integer r such that: a mod(N) = 1

x

for the function f (x) = a mod(N), gcd(a,N)=1

a, N

x

f (x)=3 mod(10)

3, 10

Period Finding

r = 4

field sieve algorithm

Conclusion

Could Quantum Supremacy be any time soon?

Counter-intuitive!

Noise and coherence

Error-Correction

Conclusion

To successfully simulate the quantum world, we need to use a machine that obeys the quantum laws of physics

Learn more about creating dynamic, engaging presentations with Prezi