April 11th, 2023: Unroll (web method) is now working for Premium users! Log in to your account page and click on the "Unroll Thread" button.

**How to get URL link on Twitter App**

- On the Twitter thread, click on or icon on the bottom

- Click again on or Share Via icon

- Click on Copy Link to Tweet

- Paste it above and click "Unroll Thread"!
- More info at Twitter Help

Day 2 of quantum advantage workshop at @InHenriPoincare, featuring Ashley Montanaro (@quantumashley), Juan Bermejo-Vega (myself) and Dominik Hangleiter. #LTQI
^{}

We kick off with Ashley Montanaro @quantumashley, giving a tutorial about IQP circuits (IQP = Instantaneous Quantum Polynomial time) and potential for demonstrating superior quantum computational performance. #LQTI
^{}

Refs:

- Shepherd, Bremner 0809.0847;

- Bremner, Jozsa, Shepherd 1005.1407;

- Bremner, Montanaro, Shepherd 1504:0799;

- Bremner, Montanaro, Shepherd 1610:01808;^{}

- Shepherd, Bremner 0809.0847;

- Bremner, Jozsa, Shepherd 1005.1407;

- Bremner, Montanaro, Shepherd 1504:0799;

- Bremner, Montanaro, Shepherd 1610:01808;

Will the day end without me having misspelled IQP at least once? Let's find out! ;)
^{}

IQP circuits are diagonal circuits in the Hadamard basis. They can encode hard to approximate output probabilities such as (conplex) Ising model partition functions (if we choose \sqrt{CZ}, To gates), and gaps of degree 3 boolean polynomials (choice: Z, CZ, CCZ gates).
^{}

These probabilities are "very hard" to compute, namely, #P-hard, i.e., harder than counting the number of solutions of a 3SAT formula in exact a. First proofs of hardness known before quantum computing was even a thing) :O
^{}

Bremner-Shepher-Jozsa: If a classical computer can exactly sample from the output distribution of IQP circuits then the Polynomial Hierarchy collapses.

arxiv.org/abs/1005.1407^{}

arxiv.org/abs/1005.1407

Today (in Ash's talks and later) we want to rule out classical simulations that imperfectly sample quantum-generated probability distributions, ie, within an ε constant additive error.
^{}

For this we will use Stockmeyer's Counting theorem: If a classical computer can efficiently sample from prob. dist. p(s), then there is an BPPNP algorithm that approximates p(s) within ε relative error, or, equivalently, an (1±ε)p(s) additive one.

cstheory.com/stockmeyer@sbc…^{}

cstheory.com/stockmeyer@sbc…

Setting epsilon to be nearly zero (zero or multiplicatively small) Stockmeyer's theorem can be used to prove Bremner-Shepherd-Jozsa's result (for the record, their original proof uses post-selection, but we will be working with Stockmeyer's today).
^{}

Bremner-Montanaro-Shepherd's 1st result -> "Approximate version" of BJS's: Assuming an additional average-case conjecture, an efficient probabilistic classical simulation of IQP circuits with an ε constant additive error implies a polynomial hierarchy collapse to its 3rd level.
^{}

Average case conjecture: random Ising model's partition functions and random 3-degree boolean polynomial's gaps are #P-hard to approximate in average. Motivation: are provably hard in worst-case, and in-built randomness doesn't intuitively simplify the average-case.
^{}

Ingredients behind BMS's proof:

1. Stockmeyer's Theorem => If a "good" additive-error classical sampler exists then a BPP^NP algorithm can approximate output probabilities with 1/poly(n) additive error. This is Good but not there Yet.^{}

1. Stockmeyer's Theorem => If a "good" additive-error classical sampler exists then a BPP^NP algorithm can approximate output probabilities with 1/poly(n) additive error. This is Good but not there Yet.

2. A proof that IQP circuits anti-concentrate => The same BPP^NP algorithm yields constant relative error approximations of output probabilities in average. But this was assumed to be #P-hard => Polynomial Hierarchy collapses to 3r level coz

BPP^NP ⊆ PH_3 ⊆ PH ⊆ P^{#P}^{}

BPP^NP ⊆ PH_3 ⊆ PH ⊆ P^{#P}

After a coffee reboot ☕️, @quantumashley will tell us more about hardness of classically simulating IQP circuits, complexity theory and implementations on physically-realistic architectures. #LTQI
^{}

More on the proof: Stockmeyer's algorithm gives you O(ε/2^n + p(s)/poly(n)) errors. The anticoncentration property ensures that a large fraction of the IQP output probabilities fulfils p(s) ≥ ε’/2^n. Hence, the additive term is smaller than a constant relative error in average.
^{}

The proof of anti-concentration combines:

- The Paley Zygmund inequality: shows that the probability of p(s) being larger than 1/2^n is proportional to 2^{2n} /(expected value of p(s)^2).

- A combinatorial proof that E(p(s)^2) ≥ 1/2^n

=> Final constant anti-concentration ratio.^{}

- The Paley Zygmund inequality: shows that the probability of p(s) being larger than 1/2^n is proportional to 2^{2n} /(expected value of p(s)^2).

- A combinatorial proof that E(p(s)^2) ≥ 1/2^n

=> Final constant anti-concentration ratio.

2nd result of Bremner-Montanaro-Shepherd, extends hardness results to "sparse" n-qubit IQP circuits. The latter can be implemented in depth O(√n log n) on a √n×√n square lattice (in average) using sorting networks and parallelization:

arxiv.org/abs/1610.01808 #LTQI^{}

arxiv.org/abs/1610.01808 #LTQI

"Sparse" means that 2-qubit gates are only applied with probability O(log n/n) to arbitrary pairs of qubits (i.e., typically, each qubit interacts with other log n qubits instead of n).
^{}

Can the result bv extended to depth much smaller than √n?? Unlikely, because then one would expect tensor network classical simulation algorithms would yield a sub-exponential algorithm for a #P-hard problem... :(
^{}

specifically, it would seemingly suggest the existence of a sub-exponential algorithm for counting 3-SAT, in violation with the counting exponential time hypothesis.
^{}

However, constant-depth can be achieved via different approaches inspired by measurement-based quantum computation (-> next talk):

- Gao, Wang, Duan: arxiv.org/abs/1607.04947

- Bermejo-Vega, Hangleiter, Schwarz, Raussendorf, Eisert: arxiv.org/abs/1703.00466

+^{}

- Gao, Wang, Duan: arxiv.org/abs/1607.04947

- Bermejo-Vega, Hangleiter, Schwarz, Raussendorf, Eisert: arxiv.org/abs/1703.00466

+

- Miller, Sanders, Miyake: arxiv.org/abs/1703.11002
^{}

The morning session ends. I cannot live tweet the next talk, but stay tuned to @fgrosshans ! #LTQI
^{}

• • •

Missing some Tweet in this thread? You can try to
force a refresh

**
Keep Current with
Dra Jara Juana Bermejo-Vega 🏳️🌈🐀 La Cuántica
**

Stay in touch and get notified when new unrolls are available from this author!

**
This Thread may be Removed Anytime!**

Twitter may remove this content at anytime! Save it as PDF for later use!

- Follow @ThreadReaderApp to mention us!
- From a Twitter thread mention us with a keyword "unroll"

`@threadreaderapp unroll`

Practice here first or read more on our help page!

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

**Become a Premium Member** ($3/month or $30/year) and get exclusive features!

**Make a small donation** by buying us coffee ($5) or help with server cost ($10)

Or Donate anonymously using crypto!

**Ethereum**

`0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E`

copy

**Bitcoin**

`3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi`

copy

Thank you for your support!

Email the whole thread instead of just a link!

Email Successfully Sent!