1 of 26

Gaussian boson sampling: quantum advantage and typical entanglement

Jun 28, 2023

Abhinav Deshpande

RMTA 2023

Based on Sci. Adv. 8, eabi7894 (2022), joint work with��Arthur Mehta, Trevor Vincent, Nicolas Quesada, Marcel Hinsche, �Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi,�Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand

2 of 26

Quantum computing

Nature works according to the laws of quantum physics

Not accounted for in models of computation studied pre-1980s (“classical” computing)
Truly quantum ways of processing information could change the notion of what is efficiently computable.

Ergo quantum computing

2

3 of 26

Interference: illustration

1

½

1

½

1

2

0

4 of 26

Interference: illustration

1

½

1

½

Born’s rule: take modulus squared to get probability (translates to intensity here)

5 of 26

Interference: illustration

1

2

0

6 of 26

On to quantum computing

7 of 26

What are quantum computers good for?

In principle, if we can build them, quantum computers would be able to factor efficiently in polynomial time: exponential speedup over best known classical algorithm!

At odds with the Extended Church-Turing thesis: any reasonable model of computation is polynomial-time equivalent to any other.

Are there fundamental limitations to building quantum computers? Or is it “merely” an engineering problem?
Do the laws of physics change in the complex regime? Are they sufficiently tested in this regime?

7

8 of 26

Quantum computational advantage

What

Quantumly beat the world’s best classical computers at something.
An impressive feat!

Why do it

Experimental refutation of the extended Church-Turing thesis
Testing quantum mechanics in “high-complexity” regime

How

Boson sampling and follow-ups
Random circuit sampling

8

- First off, I want to make the observation that the primary reason behind what makes quantum computing and, more generally, quantum physics, exciting is that they open up possibilities outside of classical physics and classical computation

Therefore, it would be nice to identify the quantum signal, or the feature that makes a system non-classical.
One way of quantifying non-classicality is through the following question, namely, is the quantum system efficiently simulable on a classical computer.
This is a question in the domain of computational complexity theory, which categorises problems into various classes.
In terms of complexity classes, we’re essentially asking what’s inside this class BQP, the set of problems efficiently solvable on a quantum computer, but outside of BPP, the set of problems efficiently solvable on a classical computer.

9 of 26

Experimental attempts

Demonstrations of random circuit sampling with 53 qubits¹ (also from USTC and Hefei²)
Boson Sampling: demonstrations with 13 modes³
Gaussian Boson Sampling: USTC experiments⁴^,5 with 100 modes and ~43 photons; also by Xanadu⁶ with 216 modes

9

¹F. Arute et al., Nature 574, 7779 (2019)

³ Bentivegna et al., Science Advances.1 (3) (2015)

⁴ Zhong et al., Science 370, 1460 (2020)

² Wu et al., PRL 127, 180501 (2021)

⁵ Zhong et al., PRL 127, 180502 (2021)

⁶ Madsen et al., Nature (2022)

10 of 26

Boson Sampling

10

¹Aaronson & Arkhipov, STOC (2011)

11 of 26

Boson Sampling

11

¹Aaronson & Arkhipov, STOC (2011)

²Valiant, TCS (1979)

12 of 26

Hardness

12

}

¹Aaronson & Arkhipov, STOC (2011)

13 of 26

Hiding

13

14 of 26

Back to hardness argument

In collision-free regime, Aaronson & Arkhipov (AA) observed that small enough submatrices look like i.i.d. Gaussian random matrices
Since each outcome is equally likely to be “the one we are interested in”, adversary has no choice but to distribute the total variation distance among all outcomes.
How much of this holds for Gaussian Boson Sampling?

14

15 of 26

Single photons not easy to generate
A solution: replace single photons by a “squeezed vacuum” state¹

15

Gaussian Boson Sampling

¹Hamilton et al. PRL 119, 170501 (2017)

16 of 26

Gaussian Boson Sampling

16

¹Hamilton et al. PRL 119, 170501 (2017)

²Kruse et al. PRA 100, 032326 (2019)

17 of 26

Gaussian Boson Sampling

17

Kruse et al. PRA (2019)

¹Hamilton et al. PRL 119, 170501 (2017)

²Kruse et al. PRA 100, 032326 (2019)

18 of 26

Our results: hiding in GBS

18

¹Aaronson & Arkhipov, STOC (2011)

²Jiang, J. Math. Phys. 50, 063302 (2009)

19 of 26

Summary: hiding in GBS

19

Regime	Status of hiding
	True
	Partial analytical & partial numerical evidence
	Numerical evidence

Hiding in other regimes for GBS: not sure if true!

Open conjecture in random matrix theory that is relevant for quantum community

20 of 26

Outlook

20

¹ Liu et al., arXiv:2105.05232

² Iosue et al., Quantum 7, 1017 (2023)

21 of 26

21

Thank You!

22 of 26

General GBS: average-case hardness

22

¹Bouland, Fefferman, Landau, Liu, arXiv:2102.01738

23 of 26

Outline

Introduction
Background
Hardness results

Hiding
Average-case hardness of computing probabilities

Algorithms to simulate GBS

Light-cone based

Outlook

23

24 of 26

Algorithms for GBS

24

¹Aaronson & Arkhipov, STOC (2011)

25 of 26

Light-cone based algorithm for (Gaussian) boson sampling

25

¹Deshpande et al., PRL 121, 030501 (2018)

26 of 26

Light-cone based algorithm for (Gaussian) boson sampling

26

²Maskara et al., arXiv:1906.04178

?

Easy

Hard

¹Deshpande et al., PRL 121, 030501 (2018)