Kunal Marwaha: notes on research papers, often with whaley research group

# These are rough notes
# September 22, 2020 (Rau 2009)
# September 10, 2020 (Fefferman et al 2016)
# August 4, 2020 (Dong et al 2020)
# July 22, 2020 (Bravyi et al 2019)
# July 16, 2020 (Karanjai et al 2018)
# July 9, 2020 (Kirby et al 2019-2020)
# July 2, 2020 (Kirby et al 2020)
# June 11, 2020 (Gilyén et al 2019)
# June 4, 2020 (Sung et al 2020)
# May 28, 2020 (Campbell 2019)
# May 21, 2020 (Childs et al 2020)
# May 14, 2020 (Huang et al 2020)
# May 7, 2020 (Mann et al 2020)

# These are rough notes

I write them primarily for cementing my own understanding. I sometimes oversimplify to help me understand the main point.

If there are errors, please let me know by email.

↸ Back to top

# September 22, 2020 (Rau 2009)

Main idea: Classifying “X-states” as the subalgebra su(2) × su(2) × u(1) of su(4)

Other thoughts:

↸ Back to top

# September 10, 2020 (Fefferman et al 2016)

Solo reading/watching: Fefferman’s talk at QIP (PreciseQMA = PSPACE)

Consider the precise succinct hamiltonian problem:

This is complete for PreciseQMA! (precise + quantum NP) = BQPSPACE

This is the power of “small gaps” + “quantumness” – both are needed to generalize to PreciseQMA.

Consider BQPSPACE = PSPACE

Another result: consider unitary quantum space (non-intermediate measurements only!)

Open questions:

↸ Back to top

# August 4, 2020 (Dong et al 2020)

(solo reading)

Main idea: new, optimization-based method to compute phase factors for QSP

Theme: Block encoding is a powerful technique!

Why QSP?
How does QSP work?
What does this paper do?
Things to clarify

What’s the relationship between the below approaches?

↸ Back to top

# July 22, 2020 (Bravyi et al 2019)

Main idea: There is a problem that 1D noiseless, 3D noisy constant depth quantum circuits solve but classical circuits need non-constant depth to solve.

The 1D problem uses the magic square game on 2 sets of n qubit pairs where qubit pair j from set 1 and k from set 2 are inputs. The classical constant-depth circuit cannot achieve much above 8/9 chance of success.

Magic square game on 2n pairs of qubits, where n=2
Magic square game on 2n pairs of qubits, where n=2
Things to clarify

↸ Back to top

# July 16, 2020 (Karanjai et al 2018)

A sub-theory is a subset of operations, closed under joint measurements.

Main idea: If a sub-theory is contextual, it needs O(n2) space to be classically simulated (vs O(n) for some noncontextual sub-theories, such as qubit stabilizer codes.) This quadratic scaling matches the Gottesman-Knill algorithm.

Things to clarify:

↸ Back to top

# July 9, 2020 (Kirby et al 2019-2020)

Main idea: A set of operators is noncontextual if commuting is transitive among the subset that do not commute with all other operators.

Noncontextuality is an extension of a classicality (where all operators pairwise commute).

It is easy to test for noncontextuality by checking if commuting is transitive.

This also means that noncontextuality implies commutativity is an equivalence relation (i.e. if operators commute, they are in a clique)

“Strongly contextual” means you can’t assign a consistent outcome to combinations of operators! The measurement set is not closed under multiplication.

For example: (XI * IX) * (ZI * IZ) is YY, but (XI * IZ) * (ZI * IX) is -YY

“Weakly contextual” means joint distributions don’t match a hidden variable theory: v(A)v(B) ≠ v(AB)

Things to clarify:

↸ Back to top

# July 2, 2020 (Kirby et al 2020)

Noncontextuality is a generalization of classical-ness.

Noncontextuality implies a hidden variable theory can explain the results of measurements

If everything has to commute or anticommute (as in with Pauli measurements), then it is easy to simulate quasi-quantized, “noncontextual” Pauli Hamiltonians! So one can simulate more than just the diagonal terms.

↸ Back to top

# June 11, 2020 (Gilyén et al 2019)

I found this talk really helpful. It started simple and ramped up very quickly.

↸ Back to top

# June 4, 2020 (Sung et al 2020)

This is from the Google collaboration. They introduced a new optimizing algorithm and compared performance by experimental demonstration with existing optimizers on common physics and CS models.

↸ Back to top

# May 28, 2020 (Campbell 2019)

This is a cool protocol, “qDRIFT”:

It’s good compared to Trotter/Suzuki since dependence on number of terms is much better (not directly on L, just on cj)

Stochastically drifts towards target unitary.

There is an interesting quantum channel argument, showing that the Taylor expansion of eitHρe − itH is close to the probabilistic mixing of gates in qDRIFT (choosing Hj with probability cj/∑cj, many times)

New ideas
Things to clarify

↸ Back to top

# May 21, 2020 (Childs et al 2020)

This is a more sophisticated theory of trotter error bounds for product formulas.

It makes these contributions:

  1. defining types of trotter error (additive vs multiplicative vs exponential)
  2. defining order conditions (rates of convergence of the errors)
  3. using “error representations” (to prove bounds on errors)

Order conditions imply that many derivatives vanish: f(t) = O(tp) means first p terms vanish (Since f is smaller than ctp near 0, f = aktk + ... + aptp ). This causes many terms to drop out.

Things to clarify

↸ Back to top

# May 14, 2020 (Huang et al 2020)

With an ensemble of unitaries, you only need a few measurements to generate a “classical shadow” (a best guess, like least squares). This can approximate a lot of linear observables without knowing what you’re looking for.

But you have to bound the shadow norm of operators.

↸ Back to top

# May 7, 2020 (Mann et al 2020)

Computing the partition function is related to approximating the ground state.

This is a polynomial approximation algorithm for quantum spin systems.

It converts the Hamiltonian into a sum of edge contributions of a graph. There are several methods to find Z(β) = Tr(e − βH):

This uses “abstract cluster expansion”. A polymer in the quantum instance (QCE) is a multiset of hyperedges, with multiplicities per hyperedge, using a connected subgraph.

I read the paper and was impressed by its presentation:

Things to clarify

↸ Back to top


Do you have a paper suggestion? Was this helpful for you? Please send me an email.