Thread by @fgrosshans

Now Dominik Hangleiter talks about getting rid of the anticoncentration conjecture in random universal circuits
#LTQI

Dominik Hangleiter: the random circuit model uses a √n×√n lattice of qubits with gates taken out of {CZ,√X,√Y, T}

#LTQI

Dominik Hangleiter: More abstractly, the unitary U outputing X is chosen at random in some family. We need the anticonconetration conjecture.

Which families of U satisfies this ? At least the 2-designs do it.
Paley-Zygmund : Pr(Z≥αE(Z))≥(1-α)²E(Z)²/E(Z²)
#LTQI

Dominik Hangleiter:
A unitary k-design is an ensemble such that ∀X∈B(H)^⊗k E_design(U^⊗k X U⁺^⊗k)=E_Haar(U^⊗k X U⁺^⊗k)
and a similar def. for states.

For an ε-approximate design, the expectation values are within a (1±ε) factor of Haar’s
#LTQI

Domink Hangleiter shows that, if U is a k-design, |ψ⟩∈ℋ, then U|ψ⟩ is a state k-design by computing the expectaton values.

Using PAley-Zygmund, for an ε-design
Pr(P_U(X)≥α(1-ε)/N) ≥ (1-α)³(1-ε)²/2(1+ε)

#LTQI

Dominik Hangleiter now needs random circuits to be ϵ-approximate designs
It’s known (thm by BHH) that G-local PRQC (parallel random local quantum random circuits) are ε-approx 2 designs in a depth ∼n log(1/ε)
⇒ G-local PRQC anticoncentrate at depth n log(1/ε)
#LTQI

Domink Hangleiter: This is worse than Google setting, which is of depth √n, but it is expected in this 1D set-up
#LTQI

Dominik Hangleiter: If one exactly synthesizes the family of IQP {SWAP, exp(-iπ/8 X⊗X)} ⇒ approx, of U are ♯P hard to simulate to ∼¼ in linear depth

The idea is to use IQP results
#LTQI