# March-April 2019 Archive

This is an archive of what I found useful, interesting, or simply enjoyable from March and April 2019.

# Research

## Stabilizer quantum mechanics

• Unbiased Simulation of Near-Clifford Quantum Circuits, Bennink et al. 2017
• Simulation of Qubit Quantum Circuits via Pauli Propagation, Rall, Liang, Cook and Kretschmer 1901.09070
• Efficient classical simulation of Clifford circuits with nonstabilizer input states, Bu and Koh 1902.11257

Let $\mathcal{C}_3$ be a circuit composed of gates from the third level of Clifford hierarchy.

Theorem 1. The output probabilities of a circuit $\mathcal{C}_3$ on $n+m$ qubits with input state $\ketbra{0}{0}^{\otimes n} \otimes^m_{j=1} \rho_j$ and computational basis measurement can be approximated up to $l_1$ norm $\delta$ in $(n+m)^{\mathcal{O}(1)} m^{\mathcal{O}\left[ \log \left( \sqrt{\alpha} /\delta \right)/\lambda \right]}.$ $\lambda$ measures the mixedness of the most pure $\rho_j$, namely the $\lambda = \epsilon$ for every qubit state of the form $(1-\epsilon)\ketbra{\psi}{\psi} + \epsilon\id/2$. The $1-2/\alpha$ comes from using the Markov inequality on the average of the $l_1$ norm of the Fourier coefficients of the output probabilities over the uniform distribution of Cliffords (a unitary 2-design). Since qudit ($d \ge 3$) Cliffords also form a 2-design, the latter technique should generalize. (The set of qubit Cliffords is not just a 2-design but also a 3-design.)

When every input state is pure, the exponent blows up. For that, we have

Theorem 2 The output probabilities of a circuit $\mathcal{C}_3$ on $n+m$ qubits with input state $\ket{0}^{\otimes n} \otimes^m_{j=1} \ket{\psi_j}$ and computational basis measurement on $k$ qubits, the number of of unmeasured qubits being greater than the log of the Pauli rank $n+m-k \ge \sum^m_{j=1} \log \left( \frac{\chi(\psi_j)}{2} \right),$ can be approximated up to $l_1$ norm $\delta$ in $(n+m)^{\mathcal{O}(1)} m^{\mathcal{O}\left[ \log \left( \sqrt{\alpha} /\delta \right)/\mu \right]},$ where now $\mu(\psi) := 2(1-\max_{\phi \in \mathrm{stab}} |\av{\phi|\psi}|^2).$ The fidelity to the closest stabilizer state is the stabilizer rank. Curiously, the more “stabilizer-ness” the worse the runtime!

The method is inspired by “Efficient classical simulation of noisy quantum computation” by Gao and Duan, and much like that paper, Bu and Koh’s paper is about average-case difficulty. Notably Gao and Duan’s paper gives a classical simulation of a random quantum circuit with constant noise, seemingly contradicting the threshold theorem, but a fault-tolerant circuit is hardly a random circuit.

• Having talked to Kaifeng Bu, I should read his “Classical simulation of quantum circuits by half Gauss sums”. Interestingly, the paper also has something to say about the “Holant function”, related to perfect matchings on weighted graphs (“matchgate tensors”).

## Representation theory

Algebraic geometry

• Linear Algebraic Groups, Humphreys 1998
• John Baez on Geometric quantization [Nautilus article on how algebraic geometry (“Hartshorne”), or rather algebraic topology finally clicked for him]

According to some school of thought, quantization is a process of taking a symplectic manifold $M$ and turn it into a complex Hilbert space (and smooth functions–classical observables–to linear operators). But that is really just a “prequantization”. Baez points out. We need much more than that; we need a line bundle $L$ over $M$ and various structures (even if $M$ is already Kähler) that make $L$ compatible with the symplectic, complex, and Riemannian structure on $M$. (This shows you how it works for 2-spheres.)

The world is quantum so perhaps it makes little sense to expect that just the symplectic structure can take us all the way to the complex Hilbert space. Instead, Baez proposing, let us start with a complex projective variety $\C P^n \subset \C^{n+1}$, then take the smallest subspace in $V \subset \C^{n+1}$ whose projectivized space $\mathbb{P}V$ contains $M$ to be its quantization $Q(M) = V$. Projectivization then gives back $P(V) = M$. In this way, we have poset categories Class of classical state spaces and Quant of quantum state spaces and a pair of adjoint functors between them. You can make them monoidal (essentially having the tensor product structure—Segre embedding for varieties) and clone the system with symmetrized product (Veronese embedding for varieties). The latter is actually how you take a classical limit of generalized coherent states (equivalently, scaling up the symplectic structure).

$HV$-varieties

• On a class of quasihomogeneous affine varieties, Popov and Vinberg 1972 [English translation: Math USSR Izvestija 6 743-58]
• Symmetry, Representations, and Invariants, Goodman and Wallach 2009 (Exercise 12.2.5.2)
• $HV$-varieties of small codimensions” in Tangents and Secants of Algebraic Varieties, Zak 1993
• On Spherical Double Cones, Littelmann 1994
• Complexity and rank of actions in invariant theory, Panyushev 1999
• Homogeneous Spaces and Equivalent Embeddings, Timashev 2011

## Linear programming

• The military refer to their various plans or proposed schedules of training, logistical supply and deployment of combat units as a program. When I first analyzed the Air Force planning problem and saw that it could be formulated as a system of linear inequalities, I called my paper Programming in a Linear Structure. Note that the term ‘program’ was used for linear programs long before it was used as the set of instructions used by a computer. In the early days, these instructions were called codes.

• Eigenvalue optimization [paywalled], Lewis and Overton 1996
• Minimizing the largest eigenvalue (minimizing the $l_{\infty}$-norm) can be written as a linear program.
• Finding the sparsest solution (minimizing the $l_0$-“norm”) is NP-hard. The standard trick is to instead optimize for the $l_1$-norm. But for the problem I’m concerning, I’m optimizing over probability vectors so that is out of the question.

# Media

• Gravity Research Foundation

his wish to overcome gravity dated from the childhood drowning of his sister. “She was unable to fight gravity, which came up and seized her like a dragon and brought her to the bottom,” he wrote.

• Dopamine: fast and slow (Fast spike or inhibition of dopamine signals the (emotionally positive or negative) error between prediction and reality, not reward. Slow dopamine is for wanting, motivation to work, not happiness.)
• The Scientists Who Make Apps Addictive (B.J. Fogg’s students went on to found Instagram and write books like Hooked: How to Build Habit-Forming Products.)

“I look at some of my former students and I wonder if they’re really trying to make the world better, or just make money,” said Fogg. “What I always wanted to do was un-enslave people from technology.”

Harris was Mike Krieger’s collaborator on Send the Sunshine in Fogg’s class of 2006. Like Krieger, Harris went on to create a real-world app, Apture, which was designed to give instant explanations of complex concepts to online readers […] Harris believed in his mission to explain, yet he could not persuade publishers that incorporating his app would lead to people spending more time on their sites. He came to believe that the internet’s potential to inform and enlighten was at loggerheads with the commercial imperative to seize and hold the attention of users by any means possible.

After working for Google for a year or so, Harris resigned […] Before leaving, he gave a farewell presentation to Google’s staff in which he argued that they needed to see themselves as moral stewards of the attention of billions of people. Unexpectedly, the slides from his talk became a viral hit inside the company, travelling all the way to the boardroom. Harris was persuaded to stay on and pursue his research at Goo­gle, which created a new job title for him: design ethicist and product philosopher. After a while, Harris realised that although his colleagues were listening politely, they would never take his message seriously without pressure from the outside. He left Google for good earlier this year […]

• Human Contact is Now a Luxury Good, NY Times
• The bad PowerPoint slide that contributes to the Space Shuttle Columbia disaster
• If you think you’re in a bad place, your life could be worse if you are Facebook moderators
• What happened to 90s environmentalism?, SSC (Do environmental problems fall out of public consciousness because they have been solved successfully or because they were just a fad all along?)
• Insect biomass declines by 75% [SA] [NYT] [HuffPost] [Guardian] (Not sure what to conclude from all these.)
• Kimura & Crow: Infinite Alleles (Wanting to “do something in genetics like what the theoretical physicists were doing in physics,” Kimura ended up writing a heat equation obeyed by neutrally-evolved genes.)
• Natural selection on weighted graphs, Quanta
• The grandmother hypothesis, Quanta
• Mutations render a woman unable to feel pain or anxiety. The mutations shut down the gene controlling FAAH which breaks down anandamide, a natural cannabis-like substance.
• Karen Uhlenback is the first woman to win the Abel Prize. (Uhlenback of the Ornstein-Uhlenback process is her father-in-law.)
• The 1993 article, The Death of Proof doesn’t age well, and the author knows it: [The Horgan Surface and the Death of Proof] [Okay, Maybe Proofs Aren’t Dying After All]
• Corn production is estimated to account for 4,300 premature deaths related to air pollution in the US per year. Ammonia from fertilizer application was by far the largest contributor to corn’s air pollution footprint. 86% of PM2.5 emissions happen on farm
• The 2019 Winter smog in Thailand seems to correlate most with fire from as far as 720 km away (Myanmar, Laos and Cambodia)
• The Day the Dinosaurs Died, New Yorker

One day sixty-six million years ago, life on Earth almost came to a shattering end. The world that emerged after the impact was a much simpler place. When sunlight finally broke through the haze, it illuminated a hellish landscape. The oceans were empty. The land was covered with drifting ash. The forests were charred stumps. The cold gave way to extreme heat as a greenhouse effect kicked in. Life mostly consisted of mats of algae and growths of fungus: for years after the impact, the Earth was covered with little other than ferns. Furtive, ratlike mammals lived in the gloomy understory. But eventually life emerged and blossomed again, in new forms.

tl;dr version:

“3 metre problem”: almost no dinosaur remains have before been found 3 metres below the so-called “KT boundary”, a layer of sediment that preserves the asteroid’s debris and ash from the extinction event.

In the 70’s, Walter (geologist) and Luis Alvarez (nuclear physicist) discovered a KT layer laced with iridium, conjectured to be from the asteroid impact. The impact crater (named Chicxulub) was found in 1991. The debate was considered largely settled in 2010 (wow!) that the asteroid caused the extinction.

The new paper is a result from the discovery dated back to 2012 by a grad student Robert DePalma of the KT site “Tanis” (a Raiders-of-the-Lost-Ark reference) at Hell Creek in North Dakota. Among the things found are preserved microtektites, a sort of glass beads or spindles that formed from molten rock ejected during the impact and solidified while re-entering the atmosphere. This suggests that the site recorded the first hours or so of the extinction event.

Geophysics problem: there was not enough time for the flood that would preserve the microtektites to reach the site from the source of impact. They conjectured that the flood was caused by seiches that can happen far away from the source, and estimated the time all kinds of different seismic waves would arrive at the site to cause such seiches (6, 10, and 13 minutes).

• Skepticism greet fossils claimed to record dinosaur-killing asteroid impact, ScienceMag
• Tax preparation companies lobby Congress to ban IRS from creating their own free tax preparation software.
• Weighted average of opinions based on prediction track records is at least as accurate as prediction markets (n=535)
• You dropped this \

### Entertainment

• A documentary on the CGI animation industry (1/n)

## Anime

• Hyouka (22 Episodes), Kyoto Animation {Honezawa Yonobu} [Novel] 2012 (Notable episodes: 17, 21)
• Mob Psycho 100 II (13 Episodes), Bones {ONE} [Webmanga] 2019
• Bakemonogatari (15 Episodes), Shaft {Nisio Isin} [Light novels] 2009, 2010 (Rewatch)

## Video games

• Touhou Luna Nights, Team Ladybug

Pros: Great pixel art and attentions to details. A number of objects interacts with time manipulation. (Yes, you play as Sakuya.) The water physics is especially cool. Cons: Snail Time and the grace mechanics makes the game really easy, in addition to the short length and the map not sprawling enough for a Metroidvania, which reminds me that I haven’t finished Rabi-Ribi. That one has a wondrous, sprawling map (and in a sense a funny comparison because it is a bullet hell game while Luna Nights is not.)

1. cvxpy needs Microsoft Visual C++ 14.0. Go and download Visual Studio 2019 (16.0) (Community). Open the installer and check “Desktop Development with C++”. To be safe, also upgrade the setuptools with pip install --upgrade setuptools

Archieves by date, by category, by tag.