We consider an error model for quantum computing that consists of contagious quantum germs that can infect every output qubit when at least one input qubit is infected. Once a germ actively causes error, it continues to cause error indefinitely for e
very qubit it infects, with arbitrary quantum entanglement and correlation. Although this error model looks much worse than quasi-independent error, we show that it reduces to quasi-independent error with the technique of quantum teleportation. The construction, which was previously described by Knill, is that every quantum circuit can be converted to a mixed circuit with bounded quantum depth. We also consider the restriction of bounded quantum depth from the point of view of quantum complexity classes.
Let $Gamma$ be a compact tropical curve (or metric graph) of genus $g$. Using the theory of tropical theta functions, Mikhalkin and Zharkov proved that there is a canonical effective representative (called a break divisor) for each linear equivalence
class of divisors of degree $g$ on $Gamma$. We present a new combinatorial proof of the fact that there is a unique break divisor in each equivalence class, establishing in the process an integral version of this result which is of independent interest. As an application, we provide a geometric proof of (a dual version of) Kirchhoffs celebrated Matrix-Tree Theorem. Indeed, we show that each weighted graph model $G$ for $Gamma$ gives rise to a canonical polyhedral decomposition of the $g$-dimensional real torus ${rm Pic}^g(Gamma)$ into parallelotopes $C_T$, one for each spanning tree $T$ of $G$, and the dual Kirchhoff theorem becomes the statement that the volume of ${rm Pic}^g(Gamma)$ is the sum of the volumes of the cells in the decomposition.
The generalized Cartan-Hadamard conjecture says that if $Omega$ is a domain with fixed volume in a complete, simply connected Riemannian $n$-manifold $M$ with sectional curvature $K le kappa le 0$, then the boundary of $Omega$ has the least possible
boundary volume when $Omega$ is a round $n$-ball with constant curvature $K=kappa$. The case $n=2$ and $kappa=0$ is an old result of Weil. We give a unified proof of this conjecture in dimensions $n=2$ and $n=4$ when $kappa=0$, and a special case of the conjecture for $kappa textless{} 0$ and a version for $kappa textgreater{} 0$. Our argument uses a new interpretation, based on optical transport, optimal transport, and linear programming, of Crokes proof for $n=4$ and $kappa=0$. The generalization to $n=4$ and $kappa e 0$ is a new result. As Croke implicitly did, we relax the curvature condition $K le kappa$ to a weaker candle condition $Candle(kappa)$ or $LCD(kappa)$.We also find counterexamples to a naive version of the Cartan-Hadamard conjecture: For every $varepsilon textgreater{} 0$, there is a Riemannian 3-ball $Omega$ with $(1-varepsilon)$-pinched negative curvature, and with boundary volume bounded by a function of $varepsilon$ and with arbitrarily large volume.We begin with a pointwise isoperimetric problem called the problem of the Little Prince. Its proof becomes part of the more general method.
We show the existence of regular combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations.
In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen structure has the required properties with positive yet tiny probability. Our method allows also to give rather precise estimates on the number of objects of a given size and this is applied to count the number of orthogonal arrays, t-designs and regular hypergraphs. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.
We analyze an upper bound on the curvature of a Riemannian manifold, using root-Ricci curvature, which is in between a sectional curvature bound and a Ricci curvature bound. (A special case of root-Ricci curvature was previously discovered by Osserma
n and Sarnak for a different but related purpose.) We prove that our root-Ricci bound implies Gunthers inequality on the candle function of a manifold, thus bringing that inequality closer in form to the complementary inequality due to Bishop.
