Open Questions

"Quantum devices can efficiently represent complex probability distributions, which are classically intractable to simulate." What is meant by this?

Possibly useful links:

• https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.117.080501
• https://www.nature.com/articles/s41567-018-0124-x
• https://www.nature.com/articles/s41567-018-0318-2

Which gates are difficult to implement (quantumly and/or classically), and when?

Clifford gates:

• Clifford gates (group can be formed from H, CNOT, S gates) are classically efficient to simulate (Gottesman-Knill theorem: stabiliser states (generated from Clifford operations applied to |0>^n state) can be described by the n generators of its stabiliser group, if these generators are represented in a tableau formalism, can represent Clifford gate operations as row/column operations on the tableau, which can be performed efficiently classically
• so any circuit composed entirely of Clifford gates cannot provide a quantum advantage
• https://www.scottaaronson.com/qclec/28.pdf

Rotations:

• All rotations can be easily formed from RZ(theta) rotation gate with a change of basis.
• Use the notation R_n = diag(1, e^{i \pi/2^{n-1}}).
• So Z = R_1 \propto R_Z(\pi), S = \sqrt{Z} = R_2, T = \sqrt{T} = R_3.
• For n>=4, cannot decompose exactly using only the standard set of universal gates => implemented probabilistically using gridsynth method.
• The cost of implementing a rotation is roughly independent of the size of the angle.
• Requires roughly 253 gates to reach precision 10^-10.

Controlled rotations:

• Controlled-R_n can be implemented with no ancillae, 2 CNOTS, 2 R_{n+1}, 1 R_{n+1}.
• This is not the most efficient method: https://www.nature.com/articles/s41598-018-23764-x.pdf

Toffoli gates: https://arxiv.org/abs/0803.2316

T gates:

• Augment Clifford group with T gates -> universal group for unitary operations (can simulate any unitary)
• (For Lila and Chiara): check talk from ceqip23, "Applications of quantum computers in ML and combinatorial optimisation" by Jens Eisert, looks into the question "At what depth does hardness kick in?", mentions increase in circuit simulation complexity from addition of T gates: can efficiently simulate with log many T gates, but not efficiently learnable after the addition of just one T gate.

What is ZX calculus useful for?

There are an increasing number of publications applying the ZX calculus formalism to new problems -- would be useful to have a list of these, along with a quick summary of the application, in a table here.