- Home
- Documents
*Quantum algorithm for P3: polar decomposition, Petz ... yquek/Slides/Petz_ ¢ Quantum...*

prev

next

out of 54

View

0Download

0

Embed Size (px)

Quantum algorithm for P3: polar decomposition, Petz recovery channels and pretty good measurements

Yihui Quek

yquek@stanford.edu

PI QI seminar

Joint work with various subsets of: András Gilyén, Seth Lloyd, Iman Marvian, Mark M. Wilde, Patrick Rebentrost

October 7, 2020

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 1 / 31

Summary of both results

Using Quantum Singular Value Transformation, we provide two quantum algorithms for two theoretical tools:

1 From classical linear algebra: polar decomposition, matrix analog of z = re iθ.

2 From quantum information: Petz recovery map, which approximately ‘reverses’ a quantum noise channel.

Application: implementation of Pretty-Good Measurements, another ubiquitous proof tool now brought to life!

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 2 / 31

Summary of both results

Using Quantum Singular Value Transformation, we provide two quantum algorithms for two theoretical tools:

1 From classical linear algebra: polar decomposition, matrix analog of z = re iθ.

2 From quantum information: Petz recovery map, which approximately ‘reverses’ a quantum noise channel.

Application: implementation of Pretty-Good Measurements, another ubiquitous proof tool now brought to life!

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 2 / 31

Quantum Singular Value Transformation

Quantum Singular Value Transformation

Block-encodings

Unitary U is a block-encoding of A if

U =

[ A/α · · ·

] ⇐⇒ A = α(〈0|⊗s ⊗ I )U(|0〉⊗s ⊗ I ). (1)

U (acts on a qubits +s ancillae) can be used to realize a probabilistic implementation of A/α.

On a-qubit input |ψ〉, Apply U to |0〉⊗s ⊗ |ψ〉 Measure ancillae; if outcome was |0〉⊗s , the first a qubits contain a state ∼ A|ψ〉.

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 4 / 31

Quantum Singular Value Transformation

Block-encodings

Unitary U is a block-encoding of A if

U =

[ A/α · · ·

] ⇐⇒ A = α(〈0|⊗s ⊗ I )U(|0〉⊗s ⊗ I ). (1)

U (acts on a qubits +s ancillae) can be used to realize a probabilistic implementation of A/α.

On a-qubit input |ψ〉, Apply U to |0〉⊗s ⊗ |ψ〉 Measure ancillae; if outcome was |0〉⊗s , the first a qubits contain a state ∼ A|ψ〉.

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 4 / 31

Quantum Singular Value Transformation

Quantum singular value transformation (I)

QSVT: A method to transform singular values of block-encodings [Gilyén-Su-Low-Wiebe’18, Low-Chuang ’16]

This circuit composes U =

[ ρ · · ·

] into

[ f̃ (ρ) · · ·

] for your choice of polynomial f̃ .

f̃ (ρ) means ‘apply f̃ to the singular values of ρ’.

Usually a polynomial approximation of ideal function f .

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 5 / 31

Quantum Singular Value Transformation

Quantum singular value transformation (II)

Uρ =

[ ρ · · ·

] QSVT−→

[ f̃ (ρ) · · ·

] Gate complexity measured in number of uses of Uρ.

Depends on approximation’s domain ([θ, 1]) and error (δ).

e.g. Can approximate x1/2 with error 1

2

∥∥∥f̃ (x)− x1/2∥∥∥ [λmin,1]

≤ δ

Let κ := 1λmin(ρ) ∼ “condition number”, overall gate complexity

O ( κ log

1

δ

) uses of Uρ.

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 6 / 31

Algorithm 1: Polar decomposition

The first P: Polar decomposition

Polar decomposition

Definition (Polar decomposition)

The polar decomposition of A ∈ CM×N is the factorization

A = UB = B̃U

where U is a unitary/isometry and B = √ A†A, B̃ =

√ AA† Hermitian.

Task: enact U := Upolar(A) on an input quantum state.

|ψ〉 → NUpolar(A)|ψ〉

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 8 / 31

The first P: Polar decomposition

Geometrical intuition for the polar decomposition

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 9 / 31

The first P: Polar decomposition

Geometrical intuition for the polar decomposition

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 9 / 31

The first P: Polar decomposition

Application of polar decomposition: Procrustes problem

Given: r (input, output) quantum state pairs: (|φi 〉, |ψi 〉)ri=1. Which U best transforms each input to output?

Figure 1: Taken from http://atlasgeographica.com/the-bed-of-procrustes/

Solution: U∗ is the polar decomposition of FG †, where F has |φi 〉 as columns and G has |ψi 〉 as columns.

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 10 / 31

http://atlasgeographica.com/the-bed-of-procrustes/

The first P: Polar decomposition

Our algorithm

[Lloyd’20] provided an algorithm for enacting Upolar(A) based on density matrix exponentiation and quantum phase estimation.

QSVT simplifies this dramatically: One realizes that

SVD(A) = r∑

i=1

σii |pi 〉〈qi | ⇒ Upolar(A) = r∑

i=1

|pi 〉〈qi |.

i.e. can simply use QSVT to set all non-zero singular values to 1.

Significant speedups

vs [Lloyd ’20]: exponentially faster in ε, with polynomial speedups in r , κ.

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 11 / 31

Algorithm 2: Petz recovery map

The second P: Petz recovery map

arxiv:2006.16924

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 13 / 31

The second P: Petz recovery map Background and intuition for the Petz map

Classical ‘reversal’ channel from Bayes’ theorem

Given input pX (x) and channel pY |X (y |x), what is pX |Y (x |y)?

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 14 / 31

The second P: Petz recovery map Background and intuition for the Petz map

Petz recovery

Classically, Bayes theorem yields ‘reverse channel’:

pX |Y (x |y) = pX (x)pY |X (y |x)

pY (y) . (2)

Quantumly: Petz recovery map! Given a forward channel, N and an ‘implicit’ input state σA:

Pσ,NB→A(·) := σ 1/2 A N †

( N (σA)−1/2(·)N (σA)−1/2

) σ

1/2 A (3)

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 15 / 31

The second P: Petz recovery map Background and intuition for the Petz map

Why should you care about the Petz map?

1 Universal recovery operation in error correction [Barnum-Knill’02, Ng-Mandayam’09]

2 Important proof tool in QI: [Beigi-Datta-Leditzky’16] as a decoder in quantum communication, achieves coherent information rate.

3

A wild Petz map has appeared in quan- tum gravity! [Cotler-Hayden-Penington- Salton-Swingle-Walter ’18]

φ (1) ab

φ (2) bc

φ (3) ab

φ (4) bc

R∗AB

R∗AB R∗BC

R∗BC

A

B

C

D

4 Is a type of quantum “Bayesian inference” [Leifer-Spekkens’13] (see: ?-product).

5 Has pretty-good measurements as a special case (later)

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 16 / 31

The second P: Petz recovery map Background and intuition for the Petz map

Why should you care about the Petz map?

1 Universal recovery operation in error correction [Barnum-Knill’02, Ng-Mandayam’09]

2 Important proof tool in QI: [Beigi-Datta-Leditzky’16] as a decoder in quantum communication, achieves coherent information rate.

3

A wild Petz map has appeared in quan- tum gravity! [Cotler-Hayden-Penington- Salton-Swingle-Walter ’18]

φ (1) ab

φ (2) bc

φ (3) ab

φ (4) bc

R∗AB

R∗AB R∗BC

R∗BC

A

B

C

D

4 Is a type of quantum “Bayesian inference” [Leifer-Spekkens’13] (see: ?-product).

5 Has pretty-good measurements as a special case (later)

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 16 / 31

The second P: Petz recovery map Background and intuition for the Petz map

Why should you care about the Petz map?

1 Universal recovery operation in error correction [Barnum-Knill’02, Ng-Mandayam’09]

2 Important proof tool in QI: [Beigi-Datta-Leditzky’16] as a decoder in quantum communication, achieves coherent information rate.

3

A wild Petz map has appeared in quan- tum gravity! [Cotler-Hayden-Penington- Salton-Swingle-Walter ’18]

φ (1) ab

φ (2) bc

φ (3) ab

φ (4) bc

R∗AB

R∗AB R∗BC

R∗BC

A

B

C

D

4 Is a type of quantum “Bayesian inference” [Leifer-Spekkens’13] (see: ?-product).

5 Has pretty-good measurements as a special case (later)

Yihui Quek (Stanford) P3: Polar, Petz, PGM October 7, 2020 16 / 31

The second P