This is an archive of what I found useful, interesting, or simply enjoyable from September to October 2019.

# Writings

You would have to live under a rock to not hear of the leaked Google’s paper and the subsequent official announcement of their demonstration of “quantum supremacy”.

- Back before the leak, I gave an online talk (organized by Quantum Technology Foundation of Thailand) in which I tried to explain what quantum supremacy really means by explaining the “collapse of the polynomial hierarchy (PH)”.

- Misunderstanding ensued after the Google’s announcement went viral (for example, that we now have a fully functional quantum computer that can break codes), which compelled me to write Google’s quantum supremacy FAQ (in Thai) targeted at an interested layperson.

# Research

## Quantum computational supremacy

### A literature review

My attempt at classifying some milestone supremacy results^{1}

Simulation | Strong | Weak | Comments |
---|---|---|---|

Worst | Aaronson’11 Bremner’10 |
(Multiplicative) Aaronson’11 Bremner’10 |
Postselection |

Average | Aaronson’11 Bouland’18 |
Conjectured(Additive) Bremner’16 Boixo’18 |
Stockmeyer Random circuits anticoncentrate |

Reviews

- Quantum computational supremacy, Harrow and Montanaro 2017
- Quantum sampling problems, BosonSampling and quantum supremacy, Lund, Bremner and Ralph 2017

Boson sampling

- The Computational Complexity of Linear Optics, Aaronson and Arkhipov 2011

Random circuit sampling

- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Bremner, Jozsa and Shepherd 2010
- Average-case complexity versus approximate simulation of commuting quantum computations, Bremner, Montanaro and Shepherd 2016
- Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model, Gao, Wang and Duan 2017
- Quantum Commuting Circuits and Complexity of Ising Partition Functions, Fujii and Morimae 2017
- The complexity of approximating complex-valued Ising and Tutte partition functions, Goldberg and Guo [Springer] 2017
- Architectures for quantum simulation showing a quantum speedup, Bermejo-Vega et al 2018
- Characterizing Quantum Supremacy in Near-Term Devices, Boixo et al 2018
- Quantum Supremacy and the Complexity of Random Circuit Sampling, Bouland, Fefferman, Nirkhe and Vazirani 2019
- Closing gaps of a quantum advantage with short-time Hamiltonian dynamics, Haferkamp et al 1908.08069
- Quantum supremacy using a programmable superconducting processor, Google AI Quantum team + collaborators 2019
- Quantum supremacy: the gloves are off, Scott Aaronson
- Supplementary information (pdf)

The paper claims

*not*to rely on the typical hardness conjecture for approximated sampling, which requires sampling from a distribution closed to the ideal distribution. (Their fidelity of 0.2% is really low.) Instead they prove that the ability to classically sample from \(F|\av{x|U|0}|^2 + (1-F)/2^n\) in time \(T\) would give a good estimate to the probability \(|\av{0|U|0}|^2\) in time \(\propto T/F\) in the complexity class AM, which lies in the third level of the polynomial hierarchy (PH). In their words, “global white noise leads to no more than a linear decrease in fidelity in classical simulation time”. Therefore, a polynomial time \(T/F\) would collapse PH to the third level. (But doesn’t the fidelity decrease exponentially with the number of qubits?) - Talk by John Martinis at Caltech

### What does an NP oracle actually do?

In my experience, the most subtle concept to correctly explain when talking about PH is the idea of an

*oracle*.An oracle for a problem \(O\) is a magical black box that can answer the question \(O\) with a single querying. Generally having access to an oracle boosts the power of a computational model. For instance, one can have an oracle for an undecidable problem; there is no Turing machine that can decide whether an arbitrary Turing machine halts or not, but an oracle for the halting problem (upon inputting a Turing machine \(M\)) would just give the one-bit answer HALT or NOT HALT in one step.

Similarly, one can have an oracle for an NP-complete problem, 3SAT for concreteness. Every Boolean formula can be expressed in the conjunctive normal form (CNF) \(\vee_j \left(\wedge_k u_{jk}\right)\) where each \(u_{jk}\) is a Boolean variable, \(j\) labels the

*clauses*, and \(k\) labels the*literals*. The problem kSAT asks if a given Boolean formula wherein each clause has \(k\) literals is satisfiable i.e. the value of each \(u_{jk}\) can be set so that the formula evaluates to TRUE. NP is the class of problems where there is a short certificate for every YES instance. For example in 3SAT, if a Boolean formula is satisfiable, I can prove it by giving you a set of satisfying arguments. SAT and 3SAT are NP-complete, while 2SAT is in P.But note the asymmetry; there is no obvious short proof that I can show to convince you that a Boolean formula is

*unsatisfiable*without trying all combinations of the Boolean variables. A class of problems such that there is a short proof for every NO instance is called coNP. Factoring is special in that both YES and NO instances can be checked quickly, so it is in \(\mathrm{NP \cap coNP}\) and is not believed to be NP-complete.For the above reason, \(\mathrm{P^{NP}}\) is believed to be larger than NP (containing both NP and coNP) because when I ask the oracle “is this Boolean formula satisfiable?”, the oracle can give the answer NO, which seems to be beyond the capability of an NP machine. Similarly, \(\mathrm{NP^{NP}}\) is believed to be larger than NP. Hence we define the polynomial hierarchy to be the infinite tower \(\mathrm{NP^{NP^{NP^{\cdots}}}}\), each level \(\Sigma_{k+1} = \Sigma_k^{\mathrm{NP}}\) appears to be more computationally powerful than the one below. (We define \(\Sigma_0 = \mathrm{P}\) and \(\Sigma_1 = \mathrm{NP}\).)

## Quantum state learning

- A Survey of Quantum Property Testing, Montanaro and Wolf 2016 [Chapter 2 handwritten notes]
Sample-optimal tomography of quantum states, Haah et al 2017

For i.i.d. \(\rho^{\otimes N}\), the trace distance decays exponentially with the rate the Chernoff information, which is between \((\ln F^{-1})/2\) and \(\ln F^{-1}\) for \(F\) the fidelity, so the fidelity is a good figure of merit for the task of distinguishing between \(\rho^{\otimes N}\) and \(\sigma^{\otimes N}\), while the single-copy trace distance tends to overestimate the sample complexity.

^{2}- Adaptive quantum state tomography improves accuracy quadratically, Mahler et al 2013
How the infidelity scales with the number of samples depends on the eigenvalues of \(\rho\) itself (and the eigenbasis of the measurement). Let \(G(\epsilon) = \sqrt{\sqrt{\rho}(\rho + \epsilon\Delta)\sqrt{\rho}}\). We will perturbatively calculate the line element \(ds^2 = 2(1-\Tr G(\epsilon))\) to second order. Begin by squaring the equation \(G = (\rho + \epsilon X + \epsilon^2 Y)\) and match powers of \(\epsilon\). \[\begin{align} \rho + \epsilon\sqrt{\rho}\Delta\sqrt{\rho} = \rho + \epsilon\left( X\rho + \rho X \right) + \epsilon^2\left( X^2 + Y\rho + \rho Y\right) \end{align}\] The first order equation is the same as saying that \(X\) is the derivative of \(\sqrt{G}\). Matrices are non-commutative and one cannot use the usual chain rule that \(d\sqrt{G} = G^{-1}dG/2\). (Indeed, should \(G^{-1}\) be on the left or on the right?) Instead, one differentiates the defining equation \(\sqrt{G}\sqrt{G} = G\) (assuming that \(G\) is diagonalizable and positive and pick the positive square root \(\sqrt{G} = \sum_{j}\sqrt{g_j}\ketbra{j}{j}\)). In the eigenbasis of \(\rho\), \[\begin{align} X_{jk} &= \frac{\sqrt{p_j p_k}\Delta_{jk}}{p_j + p_k} \\ Y_{jj} &= -\frac{\av{j|X|j}^2}{2p_j} = -\sum_k \frac{|\av{j|X|k}|^2}{2p_j} \\ \Tr Y &= - \frac{1}{2} \sum_{jk} \frac{p_k\Delta_{jk}^2}{(p_j + p_k)^2} = - \frac{1}{4} \sum_{j,k} \frac{\Delta_{jk}^2}{p_j + p_k}, \end{align}\] where the last equality is obtained by grouping each pair \((j,k)\) together, writing the sum over all pairs as the sum over \(j,k\), and multiplying by 1/2 to prevent overcounting.

The point is that when all eigenvalues are far away from zero, the first order term disappears because \(\Tr X = \Tr \Delta/2 = 0\), leaving only the result \[\begin{align} ds^2 = 2 \left( 1 - \Tr\rho - \Tr X - \frac{1}{2!}\Tr Y - O(\Delta^3) \right) = \frac{1}{4} \sum_{j,k} \frac{\Delta_{jk}^2}{p_j + p_k} + O(\Delta^3) \end{align}\] (We have “set \(\epsilon=1\)”, but \(\epsilon\) has to be small for the pertubative calculation to work so a better way to think about it is that we have absorbed \(\epsilon\) into \(\Delta\).)

However, when one or more \(p_j\) are zero, the sum over \(j\) in trace \(\Tr X = \sum_{j\neq 0} \Delta_{jj}/2\) will be restricted to those terms with nonzero \(p_j\), giving \[\begin{align} ds^2 = -\Tr \Delta + O(\Delta^2) = \sum_{j=0} \Delta_{jj} + O(\Delta^2). \end{align}\] Thus a mis-estimation of small eigenvalues of \(\rho\) blows up to linear order in the infidelity.

- Shadow Tomography of Quantum States, Aaronson 2017
Predicting Features of Quantum Systems using Classical Shadows, Huang and Küng 2019

# Media

## Links

- LIGO might be detecting a black hole-neutron star merger or something else. (“Given the vastness of the universe, ambiguous detections like S190814bv are likely to be the norm for this new, multimessenger era of astronomy”)
Talking about epistemic uncertainties without losing trust, SA

Our experiments, conducted on thousands of participants, suggest that trust is not lost if the communicators can be confident about their uncertainty. This is fine if we have a good survey, because then we can quantify our margins of error, as for unemployment. But surveys may not be reliable, and there may be extra sources of systematic bias which cast doubt on the calculated intervals.

- Theoretical Physics as a Rigorous Approach to Understand Nature, ธิปรัชต์ โชติบุตร
- A not-so-flattering history of Chinese science
- Public opinion in authoritarian states (“The purpose of censorship and thought management differs from regime to regime. The contention of this post is that for many of the most effective authoritarian systems, controlling the
*thoughts*of the ruled is secondary to shaping*social cleavages*in the population.”) Fast internet disrupts political calm in Norilsk, Russia.

“At the direction of the acting prosecutor,” a typical announcement in the municipal newspaper reads, “an examination has been conducted based on information posted on the social network known as ‘Instagram’ on the network known as ‘the internet.’”

- Indian economic reform is better than you think, SSC
- Want To Know Whether A Psychology Study Will Replicate? Just Ask A Bunch Of People
- Debunking the Stanford Prison Experiment, Le Texier 2019 [PsychCentral]
- Severely Deficient Autobiographical Memory
- Techno-superstition in the age of “explainable AI”
- What is the dog there for? “we will soon be moving to a new flight crew; one pilot and a dog. The pilot is there to feed the dog, and the dog is there to bite the pilot if he touches anything.”

The findings were dispiriting. Green and Chen found that using algorithms did improve the overall accuracy of decision-making across all conditions, but this was not because adding information and explanations enabled the humans to play a more meaningful role in the process. On the contrary, adding more information often made the human interaction with the algorithm worse. When given the opportunity to learn from the real-world outcomes, the humans became overconfident in their own judgments, more biased, and less accurate overall. When given explanations, they could maintain accuracy but only to the extent that they deferred more to the algorithm. In short, the more transparent the system seemed to the worker, the more the workers made them worse or limited their own agency.

It is important not to extrapolate too much from one study, but the findings here are consistent what has been found in other cases of automation in the workplace: humans are often the weak link in the chain. They need to be kept in check. This suggests that if we want to reap the benefits of AI and automation, we may have to create an environment that is much like that of the Skinner box, one in which humans can flap their wings, convinced they are making a difference, but prevented from doing any real damage. This is the enchanted world of techno-superstition: a world in which we adopt odd rituals and habits (explainable AI; fair AI etc) to create an illusion of control.

- Neural network reduces errors in climate models and found that we underestimate sea-level rise by 300%
- New elevation data triple estimates of global vulnerability to sea-level rise and coastal flooding, Kulp and Strauss 2019 (“Here we show – employing CoastalDEM—that 190 M people (150–250 M, 90% CI) currently occupy global land below projected high tide lines for 2100 under low carbon emissions”)

### Quantum

- Scott Aaronson on Nature’s bizarrely oversold p-bit paper
- Keep quantum computing global and open
- Generation of 2D cluster state of light for universal measurement-based quantum computing achieved simultaneously by two independent labs.
- Quantum radar demonstrated detecting an object one meter away.
- Experimental quantum Darwinism FAQ, Jess Riedel
- Quantum certification and benchmarking, Eisert et al. 1910.06343
- Lecture notes on QCVV by Martin Kliesch
- NetKet: A machine learning toolkit for many-body quantum systems, Carleo et al 2019 [github]
- Peter Wittek went missing on September 29 after an avalanche hits Mount Trishul. [GoFundMe page]

### Meditation/consciousness

- I wasted 8 years of meditation because I didn’t understand these 4 things
- Is enlightenment compatible with sex scandal?, SSC (Culasada, the author of the highly acclaimed meditation guide The Mind Illuminated, allergedly cheat on his wife.)
- New posts in multi-agent models of mind sequence
- Logarithmic scales of pleasure and pain

## Musics

- Dark Crow, Man with a Mission {Vinland Saga} [OP2] (Definitely Askeladd’s song. OP1 is Thorfinn’s song.)
- Wild Side, Ali {Beastars} [OP]
- Sayonara no Yukue, Alisa Takigawa {Owarimonogatari} [ED]
- Shiny Days, Asaka {Yuru Camp△} [OP]
- Furu Biyori, Eri Sasaki {Yuru Camp△} [ED]
- Dance of Pales piano cover by Laurence Manning
- Indivisible, Hiroki Kikuta: Indivisible / Enter the Evil (1:46 is very Soukaigi-esque) / Degenerate

### Touhou

## Manga

- Vinland Saga, Vol. 1-14 (Chapter 1-100), Yukimura Makoto
- Sono Bisque Doll wa Koi wo suru, Vol. 1-4, Fukuda Shinichi

## Anime

- Kanata no Astra (12 Episodes) Lerche {Shinohara Kenta} Manga 2019
- Dumbbell Nan Kilo Moteru? (12 Episodes) Doga Kobo {Sandrovich Yabako} Manga 2019

The nomenclature “strong” and “weak” simulation comes from Van den Nest. Terhal and DiVincenzo called the former “density computation” and the latter just simulation. A strong simulation computes an arbitrary outcome probability \(p_z\) of a quantum circuit (up to some precision) while a weak simulation samples from a probability distribution \(q_z\) closed to the ideal one. An efficient strong simulation implies an efficient weak simulation with no error \(|p_z - q_z| = 0\).↩

Suppose that the error in the trace distance is \(\tau\), then for small \(\epsilon\), \(\frac{\epsilon}{2} \le \tau \le \sqrt{\epsilon}\) because \(1-\sqrt{F} \le T \le \sqrt{1-F}\). Thus, the scaling \(O(1/\epsilon)\) in the infidelity translates to the scaling \(O(1/\epsilon^2)\) in the trace distance. Note that it doesn’t matter for small infidelity \(\epsilon\) whether we use the definition \(F(\rho,\sigma) = \left(\mathrm{Tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^2\) or its square root for the fidelity because \(\epsilon = 1-\sqrt{1-\epsilon_{\surd}} \approx \epsilon_{\surd}/2\).↩