Slides

Simulating large quantum circuits on a small quantum computer M¯aris Ozols University of Cambridge

Aram Harrow Tianyi Peng Xiaodi Wu

MIT Tsinghua University University of Oregon

Reality and dreams

Reality MIT / Innsbruck experiment Factoring 15 on a 5-qubit ion trap computer [MNM+ 16]:

Reality MIT / Innsbruck experiment Factoring 15 on a 5-qubit ion trap computer [MNM+ 16]:

IBM Quantum Experience A 5-qubit superconducting quantum computer [IBM]:

Dreams (near term) Quantum supremacy [Pre12]

Dreams (near term) Quantum supremacy [Pre12] I 30 qubits – PC with about 16 GB memory I 46 qubits – supercomputer I 50 qubits – ???

Dreams (near term) Quantum supremacy [Pre12] I 30 qubits – PC with about 16 GB memory I 46 qubits – supercomputer I 50 qubits – ???

Dreams (near term) Quantum supremacy [Pre12] I 30 qubits – PC with about 16 GB memory I 46 qubits – supercomputer I 50 qubits – ???

Approaches I Linear-optical circuits (BosonSampling) [AA11] I One clean qubit model (DQC1) [MFF14] I Commuting quantum circuits (IQP) [BJS10, BMS16] I Quantum approximate optimization algorithm [FH16] I Random quantum circuits [BIS+ 16, Fuj16]

Dreams (near term) Quantum supremacy [Pre12] I 30 qubits – PC with about 16 GB memory I 46 qubits – supercomputer I 50 qubits – ???

Approaches I Linear-optical circuits (BosonSampling) [AA11] I One clean qubit model (DQC1) [MFF14] I Commuting quantum circuits (IQP) [BJS10, BMS16] I Quantum approximate optimization algorithm [FH16] I Random quantum circuits [BIS+ 16, Fuj16]

UCSB and Google are building a 50 qubit quantum computer. They recently simulated random 42-qubit circuits on a supercomputer [BIS+ 16].

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Resource estimates for factoring [FMMC12] Factoring a 2000-bit (600 decimal digit) number requires: I

4000 logical qubits

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Resource estimates for factoring [FMMC12] Factoring a 2000-bit (600 decimal digit) number requires: I

4000 logical qubits

I

2 × 108 physical qubits

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Resource estimates for factoring [FMMC12] Factoring a 2000-bit (600 decimal digit) number requires: I

4000 logical qubits

I

2 × 108 physical qubits

I

3 × 1011 gates

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Resource estimates for factoring [FMMC12] Factoring a 2000-bit (600 decimal digit) number requires: I

4000 logical qubits

I

2 × 108 physical qubits

I

3 × 1011 gates

I

1 day of computation at a clock rate of 10 MHz

Dreams (long term) Scalable quantum computer I

factoring (breaking RSA)

I

quantum simulation

I

quantum adiabatic optimization

I

...

Resource estimates for factoring [FMMC12] Factoring a 2000-bit (600 decimal digit) number requires: I

4000 logical qubits

I

2 × 108 physical qubits

I

3 × 1011 gates

I

1 day of computation at a clock rate of 10 MHz

NSA current min key size recommendation for RSA is 3072 bits

Hybrid simulators

Quantum-classical (QC) model C

|0i |0i

y

f

f (y)

|0i

QC algorithm is given by (C, f ) where I

C is an N-qubit quantum circuit

I

N f : {0, 1} → [0, 1] is a poly-time classical function

Quantum-classical (QC) model C

|0i |0i

y

f

f (y)

|0i

QC algorithm is given by (C, f ) where I

C is an N-qubit quantum circuit

I

N f : {0, 1} → [0, 1] is a poly-time classical function

The expectation of f (y) is denoted by π (C, f ) ∈ [0, 1]

Quantum-classical (QC) model C

|0i y

|0i

f

f (y)

|0i

QC algorithm is given by (C, f ) where I

C is an N-qubit quantum circuit

I

N f : {0, 1} → [0, 1] is a poly-time classical function

The expectation of f (y) is denoted by π (C, f ) ∈ [0, 1] A simulator of (C, f ) has accuracy e if its output θ ∈ R satisfies h i 2 Pr |θ − π (C, f )| < e > 3

Parameters |0i |0i |0i N qubits |0i |0i |0i

L steps

L steps

|0i n qubits |0i |0i

Parameters L steps

|0i |0i |0i N qubits |0i |0i |0i Q exec

utions L steps

|0i n qubits |0i |0i

poly(Q, N, L) time

Simulator (Q, n)-simulator of an N-qubit QC algorithm (C, f ) is a classical poly(Q, N, L, e−1 )-time algorithm

Q exec

utions L steps

|0i n qubits |0i |0i

poly(Q, N, L, e−1 ) time

Simulator (Q, n)-simulator of an N-qubit QC algorithm (C, f ) is a classical poly(Q, N, L, e−1 )-time algorithm that outputs θ ∈ R such that h i 2 Pr |θ − π (C, f )| < e > 3 after executing at most O(Q/e2 ) circuits on an n-qubit device

Q exec

utions L steps

|0i n qubits |0i |0i

poly(Q, N, L, e−1 ) time

Extreme simulators

Fully classical simulation:

Scalable quantum computer:

( O ( 2N ) , 0 )

(O(1), N )

Extreme simulators

Hybrid simulation:

(?, n)

Fully classical simulation:

Scalable quantum computer:

( O ( 2N ) , 0 )

(O(1), N )

Warm-up

How to simulate a large circuit? |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

How to simulate a large circuit?

|0i |0i |0i |0i |0i |0i |0i |0i

|0i |0i |0i |0i |0i |0i |0i

How to simulate a large circuit? |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

How to simulate a large circuit? |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

Can we cut a gate into two?

Inspiration [BSS16] Can we classically simulate k “virtual” qubits?

k

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

Inspiration [BSS16] Can we classically simulate k “virtual” qubits? d-sparse k

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

Thm [BSS16]: This circuit has a (2O(kd) , n + 1)-simulator

Inspiration [BSS16] Can we classically simulate k “virtual” qubits? d-sparse k

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

Thm [BSS16]: This circuit has a (2O(kd) , n + 1)-simulator Proof idea: Write U = ∑i=1 ci Vi ⊗ Wi for some ci ∈ C, Vi ∈ U(2k ) and Wi ∈ U(2), and use a SWAP-test like procedure. χ

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

This would scale exponentially in n. . .

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

This would scale exponentially in n. . . . . . and we have no sparseness guarantee. . .

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

. . . if only we had 2 devices. . .

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

. . . if only we had 2 devices. . . . . . and could send one qubit back and forth. . .

How about this? not sparse

n

n

|0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

U

Claim: This has a (O(1), n + 1)-simulator on a single device!

Tensor networks

Tensors

An order-k tensor A is a k-dimensional array of complex numbers.

Tensors

An order-k tensor A is a k-dimensional array of complex numbers. Each entry Ai1 ,...,ik of A is specified by k indices i1 , . . . , ik ∈ {0, 1}.

Tensors

An order-k tensor A is a k-dimensional array of complex numbers. Each entry Ai1 ,...,ik of A is specified by k indices i1 , . . . , ik ∈ {0, 1}. There are 2k entries in total.

Tensors

An order-k tensor A is a k-dimensional array of complex numbers. Each entry Ai1 ,...,ik of A is specified by k indices i1 , . . . , ik ∈ {0, 1}. There are 2k entries in total. i1 i5

i2 A i4

i3

Tensor contraction and tensor networks Tensor contraction generalizes matrix multiplication:

∑ Ai ,m,i Bj ,j ,m = Ci ,i ,j ,j m

1

3

1 2

1 3 1 2

Tensor contraction and tensor networks Tensor contraction generalizes matrix multiplication:

∑ Ai ,m,i Bj ,j ,m = Ci ,i ,j ,j m

i3

1 2

j1

i1 A

3

1

i2 · j3

B j2

1 3 1 2

j1

i1

=

A i3

∑m

B j2

j1

i1

=

C i3

j2

Tensor contraction and tensor networks Tensor contraction generalizes matrix multiplication:

∑ Ai ,m,i Bj ,j ,m = Ci ,i ,j ,j m

1 2

j1

i1 A

3

1

i2 · j3

B

j1

i1

=

j2

i3

1 3 1 2

A

∑m

B j2

i3

=

C i3

Tensor network:

B

A C D

=

j1

i1

X

j2

States and operations An order-k tensor can be encoded by a k-qubit quantum state

|Ai : =

∑

i1 ,...,ik ∈{0,1}

Ai1 ,...,ik |i1 , . . . , ik i

States and operations An order-k tensor can be encoded by a k-qubit quantum state

|Ai : =

∑

Ai1 ,...,ik |i1 , . . . , ik i

i1 ,...,ik ∈{0,1}

More generally, it can be encoded by a linear operator with the number of input + output qubits = k

States and operations An order-k tensor can be encoded by a k-qubit quantum state

|Ai : =

∑

Ai1 ,...,ik |i1 , . . . , ik i

i1 ,...,ik ∈{0,1}

More generally, it can be encoded by a linear operator with the number of input + output qubits = k ∑i1 ,i2 Ai1 ,i2 |i1 i|i2 i

∑i1 ,i2 Ai1 ,i2 |i1 ihi2 |

∑i1 ,i2 Ai1 ,i2 hi1 |hi2 |

States and operations An order-k tensor can be encoded by a k-qubit quantum state

∑

|Ai : =

Ai1 ,...,ik |i1 , . . . , ik i

i1 ,...,ik ∈{0,1}

More generally, it can be encoded by a linear operator with the number of input + output qubits = k ∑i1 ,i2 Ai1 ,i2 |i1 i|i2 i i1 i2

∑i1 ,i2 Ai1 ,i2 |i1 ihi2 |

i2

i1

∑i1 ,i2 Ai1 ,i2 hi1 |hi2 | i1 i2 time

Cups, caps, and snakes

|Φi = ∑ |ii|ii i

I=

∑ |iihi| i

hΦ| = ∑hi|hi| i

Cups, caps, and snakes

|Φi = ∑ |ii|ii

I=

i

∑ |iihi|

hΦ| = ∑hi|hi|

i

i

The snake equation

=

=

Quantum circuits are tensor networks Quantum circuit:

|0i |0i |0i

Tensor network:

How to cut a tensornetwork

Recall the big circuit. . . |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

Recall the big circuit. . . |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i |0i

Here’s a smaller version. . . Quantum circuit:

|0i |0i |0i

Tensor network:

Here’s a smaller version. . . Quantum circuit:

|0i |0i |0i

Tensor network:

The trick!

The trick!

The trick!

The trick!

The trick!

The trick!

The trick!

If the input is missing, use the maximally entangled state |Φi (this prepares Choi states of the two half-circuits).

The trick!

If the input is missing, use the maximally entangled state |Φi (this prepares Choi states of the two half-circuits). For each wire we cut, we need to add an extra qubit.

The trick!

If the input is missing, use the maximally entangled state |Φi (this prepares Choi states of the two half-circuits). For each wire we cut, we need to add an extra qubit. Can we estimate Tr(ρΦ) using only local measurements?

The observable Φ

We want to estimate Tr(ρΦ) using local measurements!

|Φi = |00i + |11i 

1 0 Φ = |ΦihΦ| =  0 1

0 0 0 0

0 0 0 0

 1 0  0 1

The observable Φ

We want to estimate Tr(ρΦ) using local measurements!

|Φi = |00i + |11i 

1 0 Φ = |ΦihΦ| =  0 1 Φ=

0 0 0 0

0 0 0 0

 1 0  0 1

1 (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z) 2

Measuring Φ locally Here is our observable: Φ=

2 (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z) 4

Measuring Φ locally Here is our observable: Φ=

2 (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z) 4

Measuring observable Z = |0ih0| − |1ih1| means measuring in the computational basis {|0i, |1i} and outputting t ∈ {1, −1}

Measuring Φ locally Here is our observable: Φ=

2 (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z) 4

Measuring observable Z = |0ih0| − |1ih1| means measuring in the computational basis {|0i, |1i} and outputting t ∈ {1, −1} 1 4

1

1 4

1 4

1 4

X

Y

Z

t1 t2

− t1 t2

t1 t2

Measuring Φ locally Here is our observable: Φ=

2 (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z) 4

Measuring observable Z = |0ih0| − |1ih1| means measuring in the computational basis {|0i, |1i} and outputting t ∈ {1, −1} 1 4

1

1 4

1 4

1 4

X

Y

Z

t1 t2

− t1 t2

t1 t2

Multiply the final output by 2!

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately:

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I

for each missing input, use one half of

√1 | Φ i 2

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y)

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y) 3. Multiply ti from all pieces, fix sign

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y) 3. Multiply ti from all pieces, fix sign 4. Output θ = ±4m f (y) (m is the number of edge cuts)

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y) 3. Multiply ti from all pieces, fix sign 4. Output θ = ±4m f (y) (m is the number of edge cuts) By construction, E[θ ] = π (C, f ).

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y) 3. Multiply ti from all pieces, fix sign 4. Output θ = ±4m f (y) (m is the number of edge cuts) By construction, E[θ ] = π (C, f ). However, θ ∈ [−4m , 4m ] but we want   Pr |θ − π (C, f )| < e > 2/3

The full simulation y1 t1 t2 Algorithm 1. Run each piece of the circuit separately: I I I

for each missing input, use one half of √1 |Φi 2 measure all output qubits in the standard basis, get bits yi measure each remaining qubit in a random Pauli basis, get ti = ±1

2. Combine all bits of y and compute f (y) 3. Multiply ti from all pieces, fix sign 4. Output θ = ±4m f (y) (m is the number of edge cuts) By construction, E[θ ] = π (C, f ). However, θ ∈ [−4m , 4m ] but we want   Pr |θ − π (C, f )| < e > 2/3 We can guarantee this by letting θ˜ equal the average of θ over O(42m /e2 ) repetitions.

Main result

Theorem If a quantum circuit has a partition with m edges between different parts and each part can be executed on an n-qubit machine (including the extra |Φi states), then this circuit has a (16m , n)-simulator.

|begini |i:=0i |i:=i+1i

Quantum software |endi |whilei |doi

|print(i)i |i