Transcript Document

Calculation Algorithm for
Finding the Mini-Max Value in
Quantum Hypothesis Testing
加藤研太郎 / Kentaro Kato
國立清華大学 電機工程学系
Bennett
Fuchs
Holevo
Josza
佐々木
広田
富田
加藤
大崎
相馬
臼田
吾妻
@Tamagawa University, Japan
Schmecher
臼田
相馬
Lutkenhaus
Van Enk
大崎
南部
宇佐見
山崎
Bennett
Fuchs
広田
Smolin
加藤
@Oiso, Kanagawa, Japan
OUTLINE
•
•
•
•
•
•
•
Background
Quantum Hypothesis Testing
Bayes Strategy
Mini-max Strategy
Calculation Algorithm
Example
Conclusion
Alice, Bob, and Eve
Alice, the sender
cipher text
Encryption
Plaintext
Bob, the receiver
Plaintext
Decryption
Eve, the eavesdropper
Classification of Quantum Cryptography
by functions
Function
Source
BB84
4 states
Key Distribution
B92
2 states
Key Distribution
YK
2 states
Key Distribution
Y-00
M states (M>100)
Direct Encryption
Single photon
Coherent
Coherent states
[Def.] Coherent state of light (with complex amplitude
Control technique  Signal Modulation
Example)
)
Y-00 protocol
The coherent-state quantum cryptosystem by Y-00 protocol
is called
 quantum stream cipher (in JAPAN) or
 alpha-eta scheme (in USA).
--- high-speed (up to internet level; ~ Gbps)
--- long-distance (over 100km)
--- and secure
Backbone >2.5Gbps
台北ー高雄＞３００ｋｍ
東京ー大阪＞６００ｋｍ
Basic Model of Y-00
Alice: Sender
Pseudo-Random Number Generator
PRNG
Secret Key
Signal
Multi-ary Signal Modulator
(it is not single photon!)
Plaintext
Pseudo-Random Number Generator
Bob: Receiver
PRNG
Secret Key
Signal
Detector
Plaintext
System Requirements for Y-00
(1) Secret Key and PRNG (Alice and Bob)
Legitimate users, Alice and Bob, share the secret key.
Enemy, Eve, has no key.
The secret key is used for driving Pseudo-Random Number Generators (PRNG).
(2) Multi-ary Signal Modulation (Alice)
Signal Modulator is controlled by output sequences of the PRNG and Plaintext at Alice’s side.
That is, emitted signals are determined by outputs of the PRNG and Plaintext.
So far, there are two major implementation schemes:
A. Phase Shift Keying (PSK) -based quantum stream cipher (Northwestern University)
B. Intensity Modulation -based quantum stream cipher (Tamagawa University)
(3) Binary Detector (Bob)
Bob’s receiver is controlled by the output sequences of the PRNG.
The output of the PRNG determines measurement basis, so that Bob’s task is to
distinguish the binary signal belonging the basis.
Basic Model: Multi-ary signal modulator
(3’) Signal constellation and mapping rule:
(basis)
(bit)
Running key
Plaintext
Signal distance >> 1
(Example)
PSK
# of bases M= 7
# of signals 2M=14
Signal distance <<1
Pseudo Random Number Generator
True random number
Nobody can guess what is next result deterministically.
Pseudo random number
It is given by some deterministic function, but
It seems to be random:
- 0 and 1 are equiprobable,
- Long period, No correlation, etc,
M-sequence (LFSR), Kasami-sequence（嵩）, etc,
Linear Feedback Shift Resister
Initial values
ri  L1
riL
cL
cL1
r1L , r1L1 ,
, r1 , r0 
ri 2
ri 1
c1
c2
AND
AND
ri
AND
AND
＋
＋
＋
OR
OR
OR
Connection coefficients cL , cL1 ,
, c2 , c1
Given by primitive polynomial
Output ri  cL riL  cL1riL 
 c2 ri2  c1ri1
Output
r1 , r2 , r3 ,
Alice
PRNG
Secret key
7
2
Plain Text
Running key
3
Signal
Mod.
0
1
0
Basis #3
0
Basis #7
1
Basis #2
0
Bob
3
7
2
Running key
PRNG
Secret key
Receiver
Signal
0
1
0
Plain Text
Encoding/Decoding Procedures - 1/3
X. Setup:
X-1: Legitimate two users, Alice and Bob, share the secret key
.
X-2: They also have the same type PRNG.
X-3: Alice and Bob know the signal partitioning rule for signaling bases;
Signaling Basis = a set of two signals
16 PSK
Basis#0
Basis#1
Basis#2
Basis#7
X-4: Alice and Bob know the bit assignment rule for each signals;
1
0
1
0
0
1
1
0
Basis#0
Basis#1
Basis#2
Basis#7
One signal is assigned to 0 and another is to 1 in each basis.
0
1
1
0
1
1 01
01 0
0
1
0
0
1
Encoding/Decoding Procedures - 2/3
A. Encoding Procedures:
A-1: By using the secret key
, Alice ganerates pseudo-random numbers.
This output sequence of PRNG is called a running key .
A-2: From the running key , Alice determines the signaling bases for
each slot.
001 011 000 010 101 110 110 100 111 100 101 …
Basis#
#1
#3
#0
#2
#5
#6
#6
#4
#7
#4
#5
A-3: If a plaintext bit is 0, Alice sends the signal assigned to 0 in the
basis determined by PRNG, and vice versa.
Basis#
Signal
0
1
1
0
1
1
1
0
0
0
1
#1
#3
#0
#2
#5
#6
#6
#4
#7
#4
#5
…
Encoding/Decoding Procedures - 3/3
B. Decoding Procedures:
B-1: By using the secret key
, Bob generates running key
determines the signaling bases for signal detection.
and
001 011 000 010 101 110 110 100 111 100 101 …
Basis#
#1
#3
#2
#0
#5
#6
#6
#4
#7
#4
#5
B-2: For each slot, binary detection is done by using information of the bases.
0
0
If signaling basis is #2,
the decision region is
given as follows:
Received signal
by Bob
Error Free
1
B-3: Thus, Bob can get the plaintext.
1
Emitted signal
by Alice
Quantum Stream Cipher
as a random cipher
Keyword: Random cipher
Nobody can get the true ciphertext without the initial shared key.
Mesurement results are probabilistic by virtue of quantum noise
Ｙ－００
Ciphertext signal can be
measured only once.
(Quantum No-cloning Theorem)
・・・
Pattern#1
Pattern#2
Pattern#X
Yellow block stands for error bit
There are so many resulting
patterns and each of them
contains error bits
Ordinary attacks do not work anymore
Implementation Schemes for Y-00
PSK - based quantum stream cipher, (NWU)
Target: Long-distance
PSK
Intensity Modulation - based quantum stream cipher (Tamagawa)
Target: High-speed
QAM - based quantum stream cipher, (KK)
Optical QAM
Intensity Level
Close
(Eye pattern)
Open
Motivation
We wish to evaluate the security level of the cryptosystem:
What is the best receiver for an eavesdropper?
Key words
Quantum Signal Detection Theory
“Mini-max strategy”
History
Theory of Games
Hypothesis Testing
RADAR system
1928 von Neumann
Mini-max theorem
1944 von Neumann
Theory of Games
1933 Neyman and Pearson
? - 1940, UK
Two-parson game
“Cost”
“Risk”
Decision Function
Nature v.s. Observer
1940-1945, MIT RadLab
“Ideal Receiver”
1939 A.Wald
Generalization of
Neyman-Pearson Theory
1953 Middleton,
Analysis of signal detection process
by statistical hypothesis testing
1954 Peterson
Receiver design by likelihood ratio
1955 Middleton,
Formulation of Signal Detection problems
based on Decision Function
Signal Detection Theory
1960年，C.W.Helstrom，Statistical Theory of Signal Detection
1960年，D.Middleton，An Introduction to Statistical Communication Theory
Pioneering works
In 1967, Helstrom : first example of quantum signal detection problem
C.W.Helstrom, Information and Control 10, 254 (1967)
Yuen et al. : Necessary and Sufficient conditions (conjecture)
H.P.Yuen, R.S.Kennedy, M.Lax, Proc.IEEE 58, 1770 (1970)
Davies and Lewis established
a generalized quantum measurement theory
(POVM theory) beyond von Neumann theory.
E.B.Davies, J.T.Lewis, Commun.Math.Phys. 17, 239 (1970)
In 1973, Holevo : the quantum Bayes strategy
A.S.Holevo, J.Multivari.Anal. 3, 337 (1973)
In 1982, Hirota : the quantum Minimax strategy .
O.Hirota, S.Ikehara, Trans.IECE Japan E65, 627 (1982)
Quantum Hypothesis Testing
量子仮説検定
???
Quantum System
We wish to determine the state of the system with small error
Quantum Signal Detection Theory
量子信号検出理論
???
Quantum Communication System
We wish to determine which signal was transmitted with small error.
Convex Region
[Definition] Convex region (or Convex set)
Let
i.e.
be a subspace (or subset) of the K-dim vector space
. Then convex region is defined as follows:
,
Example
Convex regions (2-dim case)
(2. oval )
(3. trigon)
(1. ellipse)
(4. hexagon)
(5. tetragon)
Example
Non-convex regions (2-dim case)
Example
Convex region / Non-convex region (2-dim case)
Straight line
= Convex region
Curved line
= Non-Convex region
Set of Probability Vectors
[Probability vector]
(= Vector representation of probability distribution)
where
[Set of probability vectors]
Set of Probability Vectors
[Lemma]
The set of probability vectors is a convex set.
(Proof)
For any
relation holds:
and any
such that
, the next
Set of Probability Vectors
[Lemma]
The set of probability vectors is bounded and closed
(Proof)
See textbook
Convex Function
Let
be a real-valued function defined on a convex region
[Definition] Convex function
Convex = Convex upward =
- convex
Convex Function
[Graphical image of convex function]
[Remark]
Any convex function is defined on a convex region.
Concave Function
Let
be a real-valued function defined on a convex region
[Definition] Concave function
Concave = Convex downward =
- convex
Concave Function
[Graphical image of concave function]
[Remark]
Any concave function is defined on a convex region.
Convex functions
Concave functions
Example
Lemma
[Lemma]
Let
be a concave function of
over the
region
Assume that the partial derivatives,
are defined and
continuous over the region
with the possible exception that
.
Then the necessary and sufficient conditions on a probability
to maximize the function
over the region
are given by
with some
Quantum Hypothesis Testing
量子仮説検定
• Suppose that there are
a quantum system.
• The -the hypothesis
operator is .
hypotheses about the states of
is the proposition that its density
• We wish to determine the state of the system through
measurement.
 Hypothesis Testing
Positive Operator-Valued Measure (POVM)
正作用素値測度
• [Decision Operators:決定作用素]
• [POVM]
Positive Operator-Valued Measure (POVM)
正作用素値測度
• The probability of choosing
when
is true:
Positive Operator-Valued Measure (POVM)
正作用素値測度
• Lemma:
Let
be the set of all POVMs.
is a compact convex set.
A.S.Holevo, J.Multivar. Anals., 3, 337-394 (1973)
Bayes Costs
ベイズコスト（損失係数）
• Bayes costs:
 If we made a wrong decision, we must pay a penalty
 Penalty = Cost
 It can be denoted by a real number
• In general,
Bayes Costs
ベイズコスト（損失係数）
• Example: Radar system
The average Bayes cost
平均ベイズコスト（平均損失）
• Let
be the prior probability of
Suppose that
decision.
.
is employed for our
Then the average Bayes cost is given by
where
The average Bayes cost
平均ベイズコスト（平均損失）
[Check] Joint probability:
The average probability of error
平均誤り確率
If
, then the average Bayes cost becomes the
average probability of decision errors.
Bayes Strategy
ベイズ戦略
• A strategy minimizing the average Bayes cost for any
assignment
of cost.
• Prior probabilities are known. Under this condition we
wish to minimize the average Bayes cost.
• Bayes Problem:
Find
such that
Bayes Strategy
ベイズ戦略
• Lemma:
The optimal POVM of the Bayes problem exists.
It exists because
(1)
(2)
is compact
is continuous
Necessary and Sufficient Conditions for
Bayes strategy
• Theorem (Holevo 1973):
[A]
[B]
where
A.S.Holevo, J.Multivar. Anals., 3, 337-394 (1973)
Necessary and Sufficient Conditions for
Bayes strategy
• Remark:
The following three conditions are equivalent.
[A]
[A’]
[A”]
• By this theorem,
Necessary and Sufficient Conditions for
Bayes strategy
• Outline of the proof
 Perturbation of the average Bayes cost
（摂動計算）
 “Minimum”
Concavity of the minimum Bayes cost
• [Lemma]
The minimum Bayes cost
of .
is a concave function
Concavity of the minimum Bayes cost
• [proof]
Consider
Let
Then
and
Concavity of the minimum Bayes cost
• [proof]
Let
and let
Then
, where
, i.e.
Concavity of the minimum Bayes cost
• [proof] It is arranged to the following form:
Concavity of the minimum Bayes cost
• [proof]
Observe that
Hence
Concavity of the minimum Bayes cost
• [proof]
Hence we have
Bayes Cost Reduction Algorithm
(by Helstrom)
• Finding the closed-form expression of the minimum
Bayes cost  difficult
• But, we can find the minimum Bayes cost by using a
numerical computing algorithm.
 Helstrom’s algorithm
 Eldar’s algorithm
Helstrom’s iterative algorithm for finding the
minimum Bayes cost
• Let
be a POVM
(not necessary to be optimal)
• Choose a pair of indices
, where
• Then we can find a new POVM
such that
new
• Therefore,
• Repeating this procedure,
old
Disadvantage of Bayes strategy
• In Bayes strategy, we have assumed that
• But, it is difficult to specify the probabilities in advance.
 [Example] Eavesdropping a cryptosystem
• What kind of strategy should he/she use
when the true prior probabilities are unknown?
 Mini-max Strategy
Mini-max Problem
• Find
•
such that
is called the mini-max value
Mini-max Theorem in
Quantum Hypothesis Testing
• Theorem (Hirota & Ikehara; 広田修 & 池原止戈夫):
Mini-max Theorem in
Quantum Hypothesis Testing
• Theorem (Generalized version):
Mini-max Theorem
ミニマックス定理
• Mini-max Theorem (von Neumann):
Let
and
be convex compact sets, and
let
and
.
If
is
(a) an upper semi-continuous concave function of
for fixed
, and
(b) a lower semi-continuous convex function of
for fixed
,
then there exist
and
such that
Mini-max Strategy
ミニマックス戦略
• Theorem (Hirota & Ikehara): Necessary and sufficient
conditions for mini-max strategy (Error probability)
where we have assumed that all signals are non-orthogonal
Mini-max Strategy
ミニマックス戦略
• Theorem (General): Necessary and sufficient conditions
for mini-max strategy
Property
• Lemma:
Let
and let
Then
be the solution to the mini-max problem,
be the mini-max value. That is,
Concavity of the minimum Bayes cost
• Image
A key inequality
• Suppose that
is an optimal POVM for a given
prior probability distribution
.
• Choose indices
• From the concavity of the solution set to the minimum
average Bayes cost, we have
where
A key inequality
• Inequality
 one-parameter maximization
 concave function
 Easy to find the maximum
e.g. Golden Section Search
(W.H.Press, et al, “Numerical Recipes”, Cambridge, 2007)
Bisection Search
二分探索法
• Fact:
If
and
, then
the function has a maximum in the interval
Bisection Search
二分探索法
• Choose
such that
In this case,

has a maximum in the interval
Calculation algorithm for
finding the mini-max value
START
Initialization
A
A
Find
such that
Loop A start :
Loop B start :
B
F
F
B
Find
such that
Renewal of Data
Loop B end :
Loop A end :
E
C
E
C
YES
NO
Renewal of Data
D
D
Check:
Necessary and sufficient conditions must be satisfied.
Display and Store the result
END
Example:
Application to Optical Communications
• Mini-max Receiver for Optical Communication System
Mini-max receiver
Signal
Measurement results
To evaluate the system performance, we wish to know
the mini-max value.
Ternary Amplitude Shift-Keying (3ASK)
• Alphabet:
• Signal set:
 prior distribution:
• Receiver:
“Coherent state of light”
• Find the solution to the problem
The mini-max value for 3ASK system
(closed-form expression)
• Mini-max value
• Optimal distribution in mini-max strategy
The mini-max value for 3ASK system
(by closed-form expression)
The mini-max value for 3ASK system
(by closed-form expression)
Numerical computation by the algorithm
Numerical computation by the algorithm
Conclusion
• The mini-max theorem in Quantum
Hypothesis Testing was considered
• Calculation algorithm for finding the minimax value was shown
• Example: 3ASK
future tasks
• Tuning up the algorithm
• Application to the quantum stream cipher