Koji Maruyama Wolfram Research
(Osaka City University)
http://www.qcqis.sci.osaka-cu.ac.jp/~maruyama/c5
Mathematica cafe, 8 Sep 2012
The Joy of Quantum Information Processing
Outline
Why quantum information?
Information security Quantum cryptography
Quantum information processing
What?
What can it do? How?
Summary
Why quantum information?
Alice Bob
Information security
It could be information concerning financial businesses, national security, your credit card number, etc.
eavesdropper Information security
Need to encrypt the message.
Why quantum information?
Alice Bob
Information security Why quantum information?
The base of the present encryption schemes (RSA-type)
The overwhelming difficulty of factoring large numbers. 15 = 3 x 5 ? x ?
64,151,644,943 = 104,831 x 611,953 ? x ? 481 = 13 x 37 ? x ?
Yet, some clever algorithm might be discovered by someone.
None of the current cryptosystems are ultimately secure!
Perfectly secure communication is possible if a sequence of random numbers, i.e. key, can be shared by the sender and the receiver, and if the key is used ONLY once.
comm. channel
One-time pad (Vernam cipher)
mod. addition
Alice
plain message key
mod. addition
Bob
key
Why quantum information?
Now, the question is how to share the key…
A puzzle by Artur Ekert
Want to know which light bulb is connected with which switch. But you’re NOT allowed to get in the same room twice.
Why quantum information?
Now, the question is how to share the key…
A puzzle by Artur Ekert
Mathematicians would say, “It is impossible.” Physicists would say, “Yes, it is possible.”
The secret key distribution problem is indeed like this puzzle. Why quantum information?
Quantum mechanics is useful
Not only for the secret key distribution
But also for various information processing tasks… This is where quantum mechanics comes in
Classical information theory
‘The trick’ is simple
0, 1 Quantum information theory
(any two orthogonal states)
How to distribute a secret key Essential ingredients :
Quantum cryptography
(Linearly polarised) single photons
Measurement in a polarisation basis meas. in
PBS meas. in
Bennett & Brassard (1984)
How to distribute a secret key Essential ingredients :
Quantum cryptography
(Linearly polarised) single photons
Measurement in a polarisation basis meas. in
meas. in
How to distribute a secret key Random sequence (key) Quantum cryptography
Alice
Bob 1 0 0 1 0 1 1 0 1 0 0
‘0’ ‘1’
1 0 1 1 1 1 0 1 1 0 0
How to distribute a secret key Random sequence (key) Quantum cryptography
Alice
Bob 1 0 0 1 0 1 1 0 1 0 0
1 0 1 1 1 1 0 1 1 0 0
Common secret key
What if there was an eavesdropper Quantum cryptography
Alice
Bob 1 0 0 1 0 1 1 0 1 0 0
0 1 1 0 0 1 1 1 1 0 0 Eve
Errors inevitable!
Quantum cryptography
The (naïve) error rate induced by the intercept-resend strategy
(After post-selecting the bits for which Alice and Bob chose the same basis)
Eve chooses the right basis with probability 1/2. Eve sends the right state to Bob. No error
Eve chooses the wrong basis with probability 1/2.
Eve sends a state in the wrong basis to Bob. Bob detects it in the right state with prob 1/2, and in the wrong state with prob 1/2.
Error rate 1/4
Quantum cryptography
Error rate 1/4
More detailed analysis gives a threshold ~11%.
Alie and Bob can check the error rate by sampling a subset of the entire ‘raw’ key.
If it exceeds 1/4, the possibility of eavesdropping cannot be ruled out. Then they discard the key and redo everything (possibly changing the quantum channel, or just give up). If the error rate doesn’t exceed 1/4, the secrecy of the shared key is guaranteed.
Perfectly secure communication is possible!
Quantum information processing
What about generic quantum information processing?
initialise all registers (bits), e.g., as 00…0,
In classical information processing, computers need abilities to
perform any operations in the Boolean algebra on the bits, and output the result.
In short, it is an execution of a Boolean function
Quantum information processing
Classical computers can carry ONE of 2n possible logical states, i.e., 00…0 to 11…1.
Classical bits
‘The trick’
0, 1 Quantum bits (qubits)
If we had n (qu)bits, (at a given instant)
Quantum computers can carry ALL of 2n possible logical states, i.e., to .
thanks to the superposition of states :
(again!)
If we could
initialise the (n-qubit) system, e.g., as ,
then any information processing is possible.
In short, it is an execution of a unitary
apply an arbitrary unitary operation(s) in the 2n-dim Hilbert space , and
measure the state of any qubit in the basis ,
and subsequent measurements. Quantum information processing
So what can a quantum computer do?
Quantum computers have been shown to have more computational power than classical counterparts.
“powerful” = ability to reach a result in polynomial time in terms of the size of the input.
Able to find (prime) factors of N in polynomial time. Among a number of quantum algorithms, the prominent examples are :
Factoring algorithm (Shor, 1995)
Search algorithm (Grover, 1996)
Able to find a particular data out of a large number N of data, such as finding a specific phone number in a thick phone
directory, in time .
So what can a quantum computer do?
Quantum computers have been shown to have more computational power than classical counterparts.
Effective (fast) simulations of quantum dynamics Ex. A system of n spin-1/2 particles
Classically, we need to diagonalise 2nx2n matrices.
Formidable! Quantumly, we need only n qubits.
‘Simulate’ the real time evolution with n qubits by controlling the dynamics, so that the final results encode the desired information. Devise a controllable quantum system whose Hamiltonian can have the same form as that of interest.
What should we do to perform quantum info processing?
What are the minimum requisites? Theorem
Any unitary operation U in the 2n-dimensional Hilbert space can be decomposed into a sequence of single qubit and two-qubit controlled-NOT (CNOT) operations.
Controlled-NOT operation
0 0 0 1 1 0
0 0 0 1 1 1 Single qubit operation
Usually, U is just a rotation
The main difficulty in the implementaion
Realising the (quantum) CNOT operation (under decoherence) is very very very hard.
Many groups in the world are racing towards the reliable implementation of the CNOT.
How can we perform the CNOT on qubits?
The main difficulty in the implementaion
Realising the (quantum) CNOT operation is very very very hard. Many groups in the world are racing towards the reliable
implementation of the CNOT.
How can we perform the CNOT on qubits?
Lets exemplify a CNOT operation with ‘spin-1/2’ systems.
Electrons bound in quantum dots Superconducting qubits
Ex .
The CNOT operation with spins
Typical interaction between two spins :
The time evolution due to this for a time lapse gives a SWAP operation.
Heisenberg interaction
Thus after a time , it gives a square root of SWAP.
The CNOT operation with spins
With the , a CNOT can be constructed as
Some candidate systems
optical lattices
cavity-QED (1D)
trapped ions
trapped ions
quantum dots
trap by SAWs
Summary
Exploiting ‘information’ in quantum mechanical
regime brings us a new paradigm of information
processing.
… also useful to motivate us to deeply understand the foundations of quantum mechanics.
