Ninnat Dangniam

Ninnat Dangniam

September-October 2019 Archive

25 minute read

Epistemic status: as of December 2020, the part on quantum supremacy is obsoleted in several aspects: having worked on proposing a new quantum advantage scheme, I now have a better understanding of the intricacies of the argument myself; a pedagogical treatment of the supermacy argument can now be found in Dominik Hangleiter’s PhD thesis.

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 aimed at interested laypeople in Thai.

Research

Quantum computational supremacy

Literature review

My attempt at classifying some milestone supremacy results 1

Simulation Strong Weak Comments
Worst-case Aaronson’11
Bremner’10		 (Multiplicative)
Aaronson’11
Bremner’10		 Postselection argument
Average-case Aaronson’11
Bouland’18		 Conjectured
(Additive)
Bremner’16
Boixo’18		 Stockmeyer theorem
Random circuits anticoncentrate

Reviews

Boson sampling

Random circuit sampling

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

    • Discontinuities of the quantum Fisher information and the Bures metric, Šafránek 2017

      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

  • 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.’ ”

  • India is doing much better than before, but is it because of the economic reform?, 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%

Quantum

Meditation/consciousness

Musics

Touhou

Manga

Anime

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

  1. 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 $\abs{p_z - q_z} = 0$. ↩

  2. 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}$. ↩

Categories:

Updated:

Leave a comment

You may also enjoy

Blog migration

7 minute read

This GitHub Page blog was originally set up with the help of my friend and was forked from his repository. The blog went 404 in August last year, and now tha...

Google’s quantum supremacy FAQ (ภาษาไทย)

4 minute read

เมื่อวันที่ 23 ตุลาคม ในที่สุดเปเปอร์ของกูเกิ้ลที่รั่วไหลบนเวบไซต์ของนาซ่าก่อนจะถูกลบไปก็ได้ปรากฏในวารสาร Nature แล้ว ทำให้เกิดไฮป์ในโซเชียลมีเดียว่า “คอมพิว...