Search

We present both bijective and automated approaches to Abel-type sums, dear to Dominique Foata., Comment: 9 pages. Dedicated to Dominique Foata on his forthcoming 90th birthday

Considerable effort in experimental quantum computing is devoted to noisy intermediate scale quantum computers (NISQ computers). Understanding the effect of noise is important for various aspects of this endeavor including notable claims for achieving quantum supremacy and attempts to demonstrate quantum error correcting codes. In this paper we use Fourier methods combined with statistical analysis to study the effect of noise. In particular, we use Fourier analysis to refine the linear cross-entropy fidelity estimator. We use both analytical methods and simulations to study the effect of readout and gate errors, and we use our analysis to study the samples of Google's 2019 quantum supremacy experiment., Comment: 68 pages, 12 figures, 19 tables

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $\varepsilon>0$ and $f$ be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple $(x,y,z ,x\oplus y\oplus z)$ of vectors of $2n$ bits with exactly $n$ ones, the probability that $f(x\oplus y \oplus z) = f(x) \oplus f(y) \oplus f(z)$ is at least $1/2+\varepsilon$. The linearity testing problem, posed by David, Dinur, Goldenberg, Kindler and Shinkar, asks whether there must be an actual linear function that agrees with $f$ on $1/2+\varepsilon'$ fraction of the inputs, where $\varepsilon' = \varepsilon'(\varepsilon)>0$. We solve this problem, showing that $f$ must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the Boolean hypercube for Gowers uniformity norms. Specifically, we show that for every $k\in\mathbb{N}$, the normalized indicator function of the middle slice of the Boolean hypercube $\{0,1\}^{2n}$ is close in Gowers norm to the normalized indicator function of the union of all slices with weight $t = n\pmod{2^{k-1}}$. Using our techniques we also give a more general `low degree test' and a biased rank theorem for the slice.

In October 2019, Nature published a paper [6] describing an experimental work that was performed at Google. The paper claims to demonstrate quantum (computational) supremacy on a 53-qubit quantum computer. Since then we have been involved in a long-term project to study various statistical aspects of the Google experiment. In [30] we studied Google's statistical framework that we found to be very sound and offered some technical improvements. This document describes three main concerns (based on statistical analysis) about the Google 2019 experiment. The first concern is that the data do not agree with Google's noise model (or any other specific model). The second concern is that a crucial simple formula for a priori estimation of the fidelity seems to involve an unexpected independence assumption, and yet it gives very accurate predictions. The third concern is about statistical properties of the calibration process., Comment: 49 pages, 13 Figures, 7 Tables

In October 2019, Nature published a paper describing an experiment that took place at Google. The paper claims to demonstrate quantum (computational) supremacy on a 53-qubit quantum computer. Since September 2019 we have been involved in a long-term project to study various statistical aspects of the Google experiment. We have been trying to gather the relevant data and information in order to reconstruct and verify those parts of the Google experiment that are based on classical computations (except when the required computation is too heavy), and to perform a statistical analysis on the data. This document describes the available data and information for the Google experiment, some main questions in the evaluation of the experiment, and some of our results and plans., Comment: v3. 32 pages, 2 figures; v2 and v3 contain a few more details about the Google quantum supremacy experiment and about and our study; v3 - thorough English editing

More than ten years ago the author described a parameter $K(\rho )$ for the complexity of $n$-qubit quantum state $\rho$ and raised the conjecture (referred to as "Conjecture C") that when this parameter is superpolynomial in $n$, the state $\rho$ is not experimentally feasible (and will not be experimentally achieved without quantum fault-tolerance). Shortly afterward [6] (arXiv:1204.3404), Steve Flammia and Aram Harrow claimed that the simple easy-to-construct $W$ states are counterexamples to "Conjecture C." We point out that Flammia and Harrow's argument regarding $W$-states is incomplete. Moreover, the emergent picture from experimental progress of the past decade on noisy intermediate scale quantum (NISQ) computers suggests that $W$-states, as simple as they appear, cannot be achieved experimentally by NISQ computers, and can not be constructed without quantum fault-tolerance., Comment: 12 pages, one figure

Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine's conjecture is that the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to problems in graph theory: relating the size of the largest independent set in a graph and in a random induced subgraph of it, and bounding the size of a set of vertices intersecting every maximum-size independent set in a graph., Comment: arXiv admin note: substantial text overlap with arXiv:2103.01541, arXiv:2103.05998

This article focuses on the connection between the possibility of quantum computers, the predictability of complex quantum systems in nature, and the issue of free will., Comment: 32 pages, 7 figures

We study several extensions of the notion of perfect graphs to $k$-uniform hypergraphs., Comment: 16 pages, 2 figures. v2: major revisions

One of the most important and useful examples in discrete geometry is a finite sequence of points on the moment curve $\gamma(t)=(t,t^2,t^3,\dots ,t^d)$ or, more generally, on a {\it strictly monotone curve} in $\mathbb R^d$. These sequences as well as the ambient curve itself can be described in terms of {\it universality properties} and we will study the question: "What is a universal sequence of oriented and unoriented lines in $d$-space'' We give partial answers to this question, and to the analogous one for $k$-flats. Given a large integer $n$, it turns out that, like the case of points the number of universal configurations is bounded by a function of $d$, but unlike the case for points, there are a large number of distinct universal finite sequences of lines. We show that their number is at least $2^{d-1}-2$ and at most $(d-1)!$. However, like for points, in all dimensions except $d=4$, there is essentially a unique {\em continuous} example of a universal family of lines. The case $d=4$ is left as an open question., Comment: 21 pages, 2 figures

In this paper, we present a variety of problems in the interface between combinatorics and geometry around the theorems of Helly, Radon, Carath\'eodory, and Tverberg. Through these problems we describe the fascinating area of Helly-type theorems, and explain some of its main themes and goals.

About twenty years ago we wrote a paper, "Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels", \cite{FKN}. In it we offered several proofs of the statement that Boolean functions $f(x_1,x_2,\dots,x_n)$, whose Fourier coefficients are concentrated on the lowest two levels are close to a constant function or to a function of the form $f=x_k$ or $f=1-x_k$. Returning to the paper lately, we noticed that the presentation of the first proof is rather cumbersome, and includes several typos. In this note we rewrite that proof, as a service to the public.

We extend the famous Erd\H{o}s-Szekeres theorem to $k$-flats in ${\mathbb{R}^d}$

Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine's conjecture was the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to questions in graph theory.

We consider matrices on infinite trees which are universal covers of Jacobi matrices on finite graphs. We are interested in the question of the existence of sequences of finite covers whose normalized eigenvalue counting measures converge to the density of states of the operator on the infinite tree. We first of all construct a simple example where this convergence fails and then discuss two ways of constructing the required sequences: with random boundary conditions and through normal subgroups.

My 2018 lecture at the ICA workshop in Singapore dealt with quantum computation as a meeting point of the laws of computation and the laws of quantum mechanics. We described a computational complexity argument against the feasibility of quantum computers: we identified a very low-level complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explained why it would allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy," namely, the ability of quantum computers to make computations that are impossible or extremely hard for classical computers. We went on to describe general predictions arising from the argument and proposed general laws that manifest the failure of quantum computers. In October 2019, "Nature" published a paper describing an experimental work that took place at Google. The paper claims to demonstrate quantum (computational) supremacy on a 53-qubit quantum computer, thus clearly challenging my theory. In this paper, I will explain and discuss my work in the perspective of Google's supremacy claims., Comment: 33 pages 2 Figures. To appear in: The Intercontinental Academia, Laws: 'Rigidity and Dynamics,' (M. J. Hannon and E. Z. Rabinovici (ed.)) Proceedings of the ICA Workshops 2018\&2019, Singapore and Birmingham, World Scientific. version 2: Added section on recent developments and some minor changes

The notable claim of quantum supremacy presented by Google's team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Verifying that the generated data is indeed from the claimed distribution and assessing the circuit's noise level and its fidelity is a purely statistical undertaking. The objective of this paper is to explain the relations between quantum computing and some of the statistical aspects involved in demonstrating quantum supremacy in terms that are accessible to statisticians, computer scientists, and mathematicians. Starting with the statistical analysis in Google's demonstration, which we explain, we study various estimators of the fidelity, and different approaches to testing the distributions generated by the quantum computer. We propose different noise models, and discuss their implications. A preliminary study of the Google data, focusing mostly on circuits of 12 and 14 qubits is discussed throughout the paper., Comment: 38 pages, 9 figures (v3. some additional analysis), to appear in Statistical Science

Let $\mathbb{F}$ be a fixed field and let $X$ be a simplicial complex on the vertex set $V$. The Leray number $L(X;\mathbb{F})$ is the minimal $d$ such that for all $i \geq d$ and $S \subset V$, the induced complex $X[S]$ satisfies $\tilde{H}_i(X[S];\mathbb{F})=0$. Leray numbers play a role in formulating and proving topological Helly type theorems. For two complexes $X,Y$ on the same vertex set $V$, define the relative Leray number $L_Y(X;\mathbb{F})$ as the minimal $d$ such that $\tilde{H}_i(X[V \setminus \sigma];\mathbb{F})=0$ for all $i \geq d$ and $\sigma \in Y$. In this paper we extend the topological colorful Helly theorem to the relative setting. Our main tool is a spectral sequence for the intersection of complexes indexed by a geometric lattice., Comment: 7 pages

We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of "quantum supremacy." Some general principles governing the behavior of noisy quantum systems are derived. Our work supports the "physical Church thesis" studied by Pitowsky (1990) and follows his vision of using abstract ideas about computation to study the performance of actual physical computers., Comment: To appear in: Hemmo, Meir and Shenker, Orly (eds.) Quantum, Probability, Logic: Itamar Pitowsky's Work and Influence, Springer, Nature (2019), forthcoming

Let $\mathcal A=\{A_1,\ldots,A_n\}$ be a family of sets in the plane. For $0 \leq i < n$, denote by $f_i$ the number of subsets $\sigma$ of $\{1,\ldots,n\}$ of cardinality $i+1$ that satisfy $\bigcap_{i \in \sigma} A_i \neq \emptyset$. Let $k \geq 2$ be an integer. We prove that if each $k$-wise and $(k+1)$-wise intersection of sets from $\mathcal A$ is empty, or a single point, or both open and path-connected, then $f_{k+1}=0$ implies $f_k \leq cf_{k-1}$ for some positive constant $c$ depending only on $k$. Similarly, let $b \geq 2, k > 2b$ be integers. We prove that if each $k$-wise or $(k+1)$-wise intersection of sets from $\mathcal A$ has at most $b$ path-connected components, which all are open, then $f_{k+1}=0$ implies $f_k \leq cf_{k-1}$ for some positive constant $c$ depending only on $b$ and $k$. These results also extend to two-dimensional compact surfaces.

We consider multilinear Littlewood polynomials, polynomials in $n$ variables in which a specified set of monomials $U$ have $\pm 1$ coefficients, and all other coefficients are $0$. We provide upper and lower bounds (which are close for $U$ of degree below $\log n$) on the minimum, over polynomials $h$ consistent with $U$, of the maximum of $|h|$ over $\pm 1$ assignments to the variables. (This is a variant of a question posed by Erd\"os regarding the maximum on the unit disk of univariate polynomials of given degree with unit coefficients.) We outline connections to the theory of quasi-random graphs and hypergraphs, and to statistical mechanics models. Our methods rely on the analysis of the Gale-Berlekamp game; on the constructive side of the generic chaining method; on a Khintchine-type inequality for polynomials of degree greater than $1$; and on Bernstein's approximation theory inequality.

We propose a strengthening of the conclusion in Tur\'an's (3,4)-conjecture in terms of algebraic shifting, and show that its analogue for graphs does hold. In another direction, we generalize the Mantel-Tur\'an theorem by weakening its assumption: for any graph G on n vertices and any involution on its vertex set, if for any 3-set S of the vertices, the number of edges in G spanned by S, plus the number of edges in G spanned by the image of S under the involution, is at least 2, then the number of edges in G is at least the Mantel-Tur\'an bound, namely the number achieved by two disjoint cliques of sizes n/2 rounded up and down.

In this lecture I will talk about three mathematical puzzles involving mathematics and computation that have preoccupied me over the years. The first puzzle is to understand the amazing success of the simplex algorithm for linear programming. The second puzzle is about errors made when votes are counted during elections. The third puzzle is: are quantum computers possible?, Comment: ICM 2018 plenary lecture, Rio de Janeiro, 36 pages, 7 Figures

We make some progress on a question of Babai from the 1970s, namely: for $n, k \in \mathbb{N}$ with $k \le n/2$, what is the largest possible cardinality $s(n,k)$ of an intersecting family of $k$-element subsets of $\{1,2,\ldots,n\}$ admitting a transitive group of automorphisms? We give upper and lower bounds for $s(n,k)$, and show in particular that $s(n,k) = o (\binom{n-1}{k-1})$ as $n \to \infty$ if and only if $k = n/2 - \omega(n)(n/\log n)$ for some function $\omega(\cdot)$ that increases without bound, thereby determining the threshold at which `symmetric' intersecting families are negligibly small compared to the maximum-sized intersecting families. We also exhibit connections to some basic questions in group theory and additive number theory, and pose a number of problems., Comment: Minor change to the statement (and proof) of Theorem 1.4; the authors thank Nathan Keller and Omri Marcus for pointing out a mistake in the previous version

Chv\'{a}tal's conjecture in extremal combinatorics asserts that for any decreasing family $\mathcal{F}$ of subsets of a finite set $S$, there is a largest intersecting subfamily of $\mathcal{F}$ consisting of all members of $\mathcal{F}$ that include a particular $x \in S$. In this paper we reformulate the conjecture in terms of influences of variables on Boolean functions and correlation inequalities, and study special cases and variants using tools from discrete Fourier analysis., Comment: 15 pages

Let b(M) denote the maximal number of disjoint bases in a matroid M. It is shown that if M is a matroid of rank d+1, then for any continuous map f from the matroidal complex M into the d-dimensional Euclidean space there exist t \geq \sqrt{b(M)}/4 disjoint independent sets \sigma_1,\ldots,\sigma_t \in M such that \bigcap_{i=1}^t f(\sigma_i) \neq \emptyset., Comment: This article is due to be published in the collection of papers "A Journey through Discrete Mathematics. A Tribute to Jiri Matousek" edited by Martin Loebl, Jaroslav Nesetril and Robin Thomas, due to be published by Springer

Quantum computers are hypothetical devices, based on quantum physics, that would enable us to perform certain computations hundreds of orders of magnitude faster than digital computers. This feature is coined as "quantum supremacy" and one aspect or another of such quantum computational supremacy might be brought about in experiments in the near future: by implementing quantum error-correction, systems of non-interacting bosons, exotic new phases of matter called anyons, quantum annealing, or in various other ways. A main concern regarding the feasibility of quantum computers is that quantum systems are inherently noisy: we cannot accurately control them, and we cannot accurately describe them. We will describe an optimistic hypothesis of quantum noise that would allow quantum computing and a pessimistic hypothesis that wouldn't. The quantum computer puzzle is deciding between these two hypotheses. Here is a brief summary of the author's pessimistic point of view as explained in the paper: understanding quantum computers in the presence of noise requires consideration of behavior at different scales. In the small scale, standard models of noise from the mid-90s are suitable, and quantum evolutions and states described by them manifest a very low-level computational power. This small-scale behavior has far-reaching consequences for the behavior of noisy quantum systems at larger scales. On the one hand, it does not allow reaching the starting points for quantum fault tolerance and quantum supremacy, making them both impossible at all scales. On the other hand, it leads to novel implicit ways for modeling noise at larger scales and to various predictions on the behavior of noisy quantum systems., Comment: 25 pages, 17 predictions. This is an expanded version of a paper that appeared in the Notices of the AMS, May 2016

The classical correlation inequality of Harris asserts that any two monotone increasing families on the discrete cube are nonnegatively correlated. In 1996, Talagrand established a lower bound on the correlation in terms of how much the two families depend simultaneously on the same coordinates. Talagrand's method and results inspired a number of important works in combinatorics and probability theory. In this paper we present stronger correlation lower bounds that hold when the increasing families satisfy natural regularity or symmetry conditions. In addition, we present several new classes of examples for which Talagrand's bound is tight. A central tool in the paper is a simple lemma asserting that for monotone events noise decreases correlation. This lemma gives also a very simple derivation of the classical FKG inequality for product measures, and leads to a simplification of part of Talagrand's proof., Comment: 22 pages

Borsuk asked in 1933 if every set of diameter 1 in $R^d$ can be covered by $d+1$ sets of smaller diameter. In 1993, a negative solution, based on a theorem by Frankl and Wilson, was given by Kahn and Kalai. In this paper I will present questions related to Borsuk's problem., Comment: This is a draft of a chapter for "Surveys in Combinatorics 2015," edited by Artur Czumaj, Angelos Georgakopoulos, Daniel Kral, Vadim Lozin, and Oleg Pikhurko. The final published version shall be available for purchase from Cambridge University Press

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 every 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., Comment: 7 pages. Minor revision, discussion, and two references added in response to informal comments

We improve results of Kahn, Kalai, and Linial from the late 80s on the existence of influential large coalitions for Boolean functions, and we give counterexamples to conjectures (of Benny Chor and others) also from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions. The large gaps between the new upper and lower bounds leave a lot of room for further study., Comment: 21 pages. Some of the results are included in arXiv:1308.2794

We study the sensitivity to noise of |permanent(X)|^2 for random real and complex n x n Gaussian matrices X, and show that asymptotically the correlation between the noisy and noiseless outcomes tends to zero when the noise level is {\omega}(1)/n. This suggests that, under certain reasonable noise models, the probability distributions produced by noisy BosonSampling are very sensitive to noise. We also show that when the amount of noise is constant the noisy value of |permanent(X)|^2 can be approximated efficiently on a classical computer. These results seem to weaken the possibility of demonstrating quantum-speedup via BosonSampling without quantum fault-tolerance., Comment: Version 2: A few corrections and additions

We introduce a notion of bipartite minors and prove a bipartite analog of Wagner's theorem: a bipartite graph is planar if and only if it does not contain $K_{3,3}$ as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests. We then establish a recursive characterization of bipartite $(2,2)$-Laman graphs --- a certain family of graphs that contains all maximal bipartite planar graphs., Comment: 9 pages

We develop a bipartite rigidity theory for bipartite graphs parallel to the classical rigidity theory for general graphs, and define for two positive integers $k,l$ the notions of $(k,l)$-rigid and $(k,l)$-stress free bipartite graphs. This theory coincides with the study of Babson--Novik's balanced shifting restricted to graphs. We establish bipartite analogs of the cone, contraction, deletion, and gluing lemmas, and apply these results to derive a bipartite analog of the rigidity criterion for planar graphs. Our result asserts that for a planar bipartite graph $G$ its balanced shifting, $G^b$, does not contain $K_{3,3}$; equivalently, planar bipartite graphs are generically $(2,2)$-stress free. We also discuss potential applications of this theory to Jockusch's cubical lower bound conjecture and to upper bound conjectures for embedded simplicial complexes., Comment: Improved presentation, figure added, proof of the Deletion Lemma corrected, to appear in Trans. Amer. Math. Soc

Richman games are zero-sum games, where in each turn players bid in order to determine who will play next [Lazarus et al.'99]. We extend the theory to impartial general-sum two player games called \emph{bidding games}, showing the existence of pure subgame-perfect equilibria (PSPE). In particular, we show that PSPEs form a semilattice, with a unique and natural \emph{Bottom Equilibrium}. Our main result shows that if only two actions available to the players in each node, then the Bottom Equilibrium has additional properties: (a) utilities are monotone in budget; (b) every outcome is Pareto-efficient; and (c) any Pareto-efficient outcome is attained for some budget. In the context of combinatorial bargaining, we show that a player with a fraction of X% of the total budget prefers her allocation to X% of the possible allocations. In addition, we provide a polynomial-time algorithm to compute the Bottom Equilibrium of a binary bidding game., Comment: A preliminary version of this paper appeared in the 16th ACM Conference on Economics and Computation (EC-2015). Paper accepted to Games and Economic Behavior

We give counterexamples to a conjecture of Benny Chor and another of the second author, both from the late 80s, by exhibiting functions for which the influences of large coalitions are unexpectedly small relative to the expectations of the functions., Comment: 13 pages

The feasibility of computationally superior quantum computers is one of the most exciting and clear-cut scientific questions of our time. The question touches on fundamental issues regarding probability, physics, and computability, as well as on exciting problems in experimental physics, engineering, computer science, and mathematics. We propose three related directions towards a negative answer. The first is a conjecture about physical realizations of quantum codes, the second has to do with correlations in stochastic physical systems, and the third proposes a model for quantum evolutions when noise accumulates. The paper is dedicated to the memory of Itamar Pitowsky., Comment: 16 pages

The Gibbard-Satterthwaite theorem states that every non-dictatorial election rule among at least three alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with a non-negligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range., Comment: 27 pages, extended version of a FOCS'08 paper, to appear in SICOMP

A key fact in the theory of Boolean functions $f : \{0,1\}^n \to \{0,1\}$ is that they often undergo sharp thresholds. For example: if the function $f : \{0,1\}^n \to \{0,1\}$ is monotone and symmetric under a transitive action with $\E_p[f] = \eps$ and $\E_q[f] = 1-\eps$ then $q-p \to 0$ as $n \to \infty$. Here $\E_p$ denotes the product probability measure on $\{0,1\}^n$ where each coordinate takes the value $1$ independently with probability $p$. The fact that symmetric functions undergo sharp thresholds is important in the study of random graphs and constraint satisfaction problems as well as in social choice.In this paper we prove sharp thresholds for monotone functions taking values in an arbitrary finite sets. We also provide examples of applications of the results to social choice and to random graph problems. Among the applications is an analog for Condorcet's jury theorem and an indeterminacy result for a large class of social choice functions.

In this paper we consider adversarial noise models that will fail quantum error correction and fault-tolerant quantum computation. We describe known results regarding high-rate noise, sequential computation, and reversible noisy computation. We continue by discussing highly correlated noise and the "boundary," in terms of correlation of errors, of the "threshold theorem." Next, we draw a picture of adversarial forms of noise called (collectively) "detrimental noise." Detrimental noise is modeled after familiar properties of noise propagation. However, it can have various causes. We start by pointing out the difference between detrimental noise and standard noise models for two qubits and proceed to a discussion of highly entangled states, the rate of noise, and general noisy quantum systems., Comment: 50 pages

We propose and discuss two conjectures on the nature of information leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as required by fault-tolerant quantum computation. The first conjecture asserts that information leaks for a pair of substantially entangled qubits are themselves substantially positively correlated. The second conjecture asserts that in a noisy quantum computer with highly entangled qubits there will be a strong effect of error synchronization. We present more general conjectures for arbitrary noisy quantum systems., Comment: A revision and an extension of the formal part of quant-ph/0607021. The paper contains new conjectures on general quantum systems and elaborate on the connection with quantum error-correction

Let X be a simplicial complex on the vertex set V. The rational Leray number L(X) of X is the minimal d such that the rational reduced homology of any induced subcomplex of X vanishes in dimensions d and above. Let \pi be a simplicial map from X to a simplex Y, such that the cardinality of the preimage of any point in |Y| is at most r. It is shown that L(\pi(X)) \leq r L(X)+r-1. One consequence is a topological extension of a Helly type result of Amenta., Comment: 9 pages