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

## # 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.

## # September 22, 2020 (Rau 2009)

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

• An “X-state” is a 4 × 4 Hermitian matrix that’s zero except on both diagonals. Described by 7 real parameters. Bell state included.

• Can be represented by elements on the Fano plane (triangle with circle inside). It has one fully commuting element, and each of other 6 is part of two sets of anti-commuting elements, plus 1 “conjugate” (commuting) element.
• This representation makes it easier to do calculations on X-states (for things like “quantum discord” and “concurrence”)
• Making an X-state: ρ + X1ρX1 where X1 is the fully commuting element.
• (Each of 15 operators in su(4) commutes with 6 and anticommutes with the other 8)
• There are 15 possible su(2) × su(2) × u(1) subalgebras. Some represent different things.
• Can be viewed as a stabilizer
• If your H is an X-state, and you’re in an X-state, you’ll stay in an X-state!
• If you sandwich with another Pauli operator, It may be become an X-state in a new representation
##### Other thoughts:
• Can be viewed as two independent qubits plus a phase shift u(1)
• How is this related to two Bloch spheres?
• Can model dissipation as an X-state
• What do the non-equivalent X-states look like? Are any of them useful?
• In su(2) × su(2) what restrictions on g make it a pure state? (as an analogy to I/2 + a⃗ ⋅ σ⃗/2 is pure iff ||a⃗|| = 1) Is there a way to categorize it?

## # September 10, 2020 (Fefferman et al 2016)

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

Consider the precise succinct hamiltonian problem:

• “succinct encoding” = can get elements of row of 2k × 2k matrix in poly(n) time, k(n) space
• generalization of sparsity condition (when k(n) is poly(n))
• “precise” -> inverse exponential gap 2 − O(k(n)) (usually inverse polynomial)

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

• BQPSPACE(k) is bounded error quantum algorithm, k(n) qubits space, at most exponential runtime
• Promise problem, but error can be inverse polynomial with amplitude amplification

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

• recent paper says this is the same as non-unitary BQPSPACE, you don’t need to add ancillas!

• k-local hamiltonian problem is qma complete (verify yes/no with quantum circuit, above some error)

• can do well conditioned matrix inversion.

##### Open questions:
• What’s QMA vs QMA(2)? Where you have poly vs two Merlins that give you a result to verify?
• How does QMA(k) differ from QIP(k)?

## # August 4, 2020 (Dong et al 2020)

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

Theme: Block encoding is a powerful technique!

##### Why QSP?
• Goal is to implement matrix polynomials with few ancilla qubits
• Useful for hamiltonian simulation n e − iAt, eigenvalue filtering, QLSP (A − 1), thermal state e − βA
##### How does QSP work?
• Approximate with a polynomial function f(x), then encode f(A) exactly via block-encoding
• QSP uses adjustable phase factors, but it’s hard to find phase factors given f(x)
• It involves an “iterate” matrix. Taking an initial A as an LCU, then block encoding it, the eigenvalues of block encoding are related to A.
• QSP uses D iterates and D+1 rotations (with a phase factor for each of D+1 angles).(Similar to QAOA!)
##### What does this paper do?
• This presents a loss function, when optimized, finds the best angles to choose. (You need to guess well!)
• It uses the “Remez exchange algorithm” to reduce the approximations required.
• This work makes an insight about the decay of phase factors as related to the decay of Chebyshev polynomials.
##### Things to clarify

What’s the relationship between the below approaches?

• QSVT
• HHL algorithm for matrix function f(A)
• LCU method
• QSP
• QAOA
• qubitization

## # 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.

##### Things to clarify
• What is the X-type part of P(s)?

## # 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:
• Where else does contextuality imply simulation hardness?
• What about operations that are not closed?

## # 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:
• How does the PBR proof work, exactly?
• When can you tell if something is weakly contextual?
• What do these things mean quantitatively, outside of Pauli operators?
• What about computability (things can be classically hard but still noncontextual)

## # 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.

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

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

• Unifying perspective on quantum walks, amplitude amplification, phase estimation, Grover diffusion
• Quantum walks and repeated operators
• Take unitary U, but just look at the top part A
• But also you can make a singular value decomposition!
• You can implement a function on the singular values on A!!
• This is more general than a function on the eigenvalues (can be non-square)
• A is arbitrary. It depends on the polynomial function you want to implement on the singular values! (just has to be an odd polynomial function)
• Low degree approximate polynomials is the key.
• Lots of other possibilities (QMA amplification)

## # 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.

## # May 28, 2020 (Campbell 2019)

This is a cool protocol, “qDRIFT”:

• Split up H into normalized Hj with constants cj
• Randomly use unitaries eitHj with probability cj/∑cj
• With enough gates, it will approximate eitH (wow!)

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
• Is there a higher-order qDRIFT?
• What about H = H_a + H_b, using qDRIFT on each one? (Perhaps we can partition the terms so that [Ha, Hb] ≈ 0 ?
• What if you have one big λ and a lot of little corrections? Can you run qDRIFT on the little corrections and make HA + Hqdrift?
##### Things to clarify
• What is “compilation”?
• Why does qdrift perform so much better than trotter? even numerically?
• How does this compare to time dependent perturbation theory?

## # 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
• What improvements did Su & Childs make before this?
• Eq 10 was tricky – how do you get the R(t) part?
• Lemma 2: proof isn’t clear to me: A + e − At2BeAt2 = H? Maybe the exponentials are constants?
• How is corollary 5 proved?
• pth order condition seems pretty crucial!
• How do you get eq 30?

## # 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.

## # 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):

• correlation decay analysis
• MCMC
• interpolation

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.

• This is possible because at high temperature, β is bounded
• The truncation of the subgraph measures the locality

I read the paper and was impressed by its presentation:

• Main results up front, with clear introduction, explanation of definitions (like “fully polynomial approximation scheme”)
• Neat sections, with explanations of the sections at the end of the introduction
• Appendices for the equation manipulation
##### Things to clarify
• Why is the degree O(log d Delta)? Why is it not just Delta?
• ∼ is a symmetric compatibility relation such that each polymer is incompatible with itself … what is this? Any symmetric subset of P(X) where (a, a) is not included?
• Why is Z(C, w) the form it is?
• Why is the Ursell function involved?
• Is V(H) the number of vertices in the graph? Is this just |Gamma|?
• The summation is the sum of connected, spanning subsets of edges?
• This will only have a value for clusters!
• I didn’t walk through Lemma 2, 4, 6, 7
• Lemma 5:
• All connected subgraphs of size at most m – why can it be done in |V|em?
• Why are there (m-1 choose n-1) polymers of size at most m?
• Lemma 8: how many clusters are there? |V|O(1)