Monthly Archives: November 2008

Would you decide the election if you could?

One mental experiment I am fond of asking people (usually before elections) is this:

Suppose that just a minute before the votes are counted you can change the outcome of the election (say, the identity of the winner, or even the entire distribution of ballots) according to your own preferences. Let’s assume that this act will be completely secret. Nobody else will ever know it.

Will you do it?

You can answer in this poll: 

Impagliazzo’s Multiverse

Update (July 2009): Here are links to a related post on Lipton’s blog, and a conference announcement on Russell’s possible worlds.

On the occasion of Luca’s post on his FOCS 2008 tutorial on average-case complexity here is a reminder of Russell Impagliazzo’s description of the possible universes we live in.

Being at FOCS was a splendid experience and my presentation of the paper of Ehud Friedgut, Noam Nisan and myself was well accepted. (And reported by Rahul Santhanam on “Computational Complexity“) The slides are here; Initially I felt bad for including only one out of three parts of the proof but eventually I had no time to describe any part of the proof.

Russell Impagliazzo’s multiverse – cryptography and complexity

Impaglliazzo’s paper deals with two central topics in theoretical computer science: Computational complexity studies the power of computers and cryptography studies the ability to create codes and to hide information. These two areas added beautiful new scientific insights, and the deep connections between them were described by computer scientist Shafi Goldwasser as “a match made in heaven.” The limited power of computers and the well known question “whether P=NP” are of central importance in Impaglliazzo’s classification,  as are the concepts of “one way functions” and “public keys”.


In this universe computers can quickly solve hard problems.  (In technical terms: P=NP.)  If you can quickly recognize a valid solution to a problem once the latter is presented to you,  (such problems are “in NP”), then you can apply this same method in order to actually find a solution! In this universe almost all optimization problems have a quick and automatic solution. No cryptography is possible and therefore there is no privacy.


Muhammad ibn Musa al-Khwarizmi (the term “algorithm” is called after his name, and not after All Gore as commonly believed)


In this universe Continue reading

Detrimental Noise

 “Imagine there’s no heaven, it’s easy(?) if you try,”   

John Lennon 


Disclaimer: It is a reasonable belief  (look here, and here), and an extremely reasonable working assumption (look  here) that computationally superior quantum computers can be built.   

(This post and the draft will be freely updated) I am struggling to meet the deadline of a week ago for a chapter regarding adversarial noise models for quantum error correction. (Update Nov 20: here is the draft; comments are welcomed. Update April 23: Here is the arxived paper, comments are welcome! ) My hypothetical model is called “detrimental.” (This is a reason substantial math postings are a bit slow recently; but I hope a few will come soon.) This project is quite central to my research in the last three years, and it often feels like running, over my head, after my own tail that might not be there. So this effort may well be a CDM (“career damaging move”) but I like it nevertheless. It is related to various exciting conceptual and foundational issues. 

I do have occasionally a sense of progress, (often followed by a backtrack) and for this chapter, rather than describing detrimental noise by various (counterintuitive) properties as I always did, I think I have an honest definition of detrimental noise. Let me tell you about it. (Here is a recent useful guide: a zoo of quantum algorithms, produced by Stephen Jordan.)

Detrimental noise

Consider a quantum memory with n qubits at a state \rho_0. Suppose that \rho_0 is a tensor product state. The noise affecting the memory in a short time interval can be described by a quantum operation E_0. Lets suppose that E_0 acts independently on different qubits and, for qubit i with some small probability p_iE_0 changes it state to the maximum entropy state \tau_i.

This is a very simple form of noise that can be regarded as basic to understanding the standard models of noise as well as of detrimental noise.

In the standard model of noise, E_0 describes the noise of the quantum memory regardless of the state \rho stored in the memory. This is a quite natural and indeed expected form of noise.

A detrimental noise will correspond to a scenario in which, when the quantum memory is at a state \rho and \rho= U \rho_0, the noise E will be U E_0 U^{-1}. Such noise is the effect of first applying E_0 to \rho_0 and then applying U to the outcome noiselessly.

Of course, in reality we cannot perform U instantly and noiselessly and the most we can hope for is that \rho will be the result of a process. The conjecture is that a noisy process leading to \rho will be subject to noise of the form we have just described. A weaker weaker conjecture is that detrimental noise is present in every natural noisy quantum process. I also conjecture that damaging effects of the detrimental noise cannot be canceled or healed by other components of the overall noise.When we model a noisy quantum system either by a the qubits/gates description or in other ways we make a distinction between “fresh” errors which are introduced in a single computer cycle (or infinitesimally when the evolution is described by a continuous model) and the cumulative errors along the process. The basic insight of fault tolerant quantum computing is that if the incremental errors are standard and sufficiently small then we can make sure that the cumulated errors are as well. The conjecture applies to fresh errors.

 (Updated: Nov 19; sorry guys, the blue part is over-simplified and incorrect; But an emergency quantifier replacement seemed to have helped; it seems ok now)  The definition of detrimental noise for general quantum systems that we propose is as follows:

A detrimental noise of a quantum system at a state \rho commutes with every some non-identity quantum operation which stabilizes \rho.

Note that this description,

Just like for the standard model of noise, we do not specify a single noise operation but rather gives an envelope for a family of noise operations.

In the standard model of noise the envelope \cal D_{\rho} of noise operations when the computer is at state \rho does not depend on \rho. For detrimental noise there is a systematic relation between the envelope of noise operations {\cal D}_\rho and the state \rho of the computer. Namely,

 {\cal D}_{U\rho} = U {\cal D}_\rho U^{-1}.

Why is it detrimental?

Detrimental noise leads to highly correlated errors when the state of the quantum memory is highly entangled. This is quite bad for quantum error-correction, but an even more devastating property of detrimental noise is that the notion of “expected number of qubit errors” becomes sharply different from the rate of noise as measured by fidelity or trace distance. Since conjugation by a unitary operator preserves fidelity-metric, the expected number of qubit errors increases linearly with the number of qubits for highly entangled states.

Here is another little thing from my paper that I’d like to try on you:

A riddle: Can noise remember the future?

Suppose we plan a process and carry it out up to a small amount of errors. Can there be a systematic relation between the errors at some time and the planned process at a later time? Continue reading

Greg’s Dinosaurs Riddle

The two-riddles post was a success, and while corresponding with Greg Kuperberg he had a riddle for me about dinosaurs, and he agreed I will share it with you.

Right before the Chixculub asteroid hit the earth, there were a variety of mammals and a wide variety of dinosaurs.  Both the mammals and the dinosaurs lived in many places, came in many sizes, etc.  Why did some of the mammals survive, but none of the dinosaurs did?

A nuch simpler question: Can you answer (without clicking or googeling or so):

How many years did the dinosaurs live? (you know,.. not a single one but them as a whole…) 1 million years, 5 millions, 20 millions, 50 millions, 100 millions?

And a deep philosophical question:

The dinosaurs perished. Should we regard them as losers??? 


A Diameter Problem (6): Abstract Objective Functions

Dantzig and Khachyan

George Dantzig and Leonid Khachyan

In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for these directed graphs are the directed graphs of polytopes where the direction of the edges is described by a linear objective function.  

7. Linear programming and the simplex algorithm.

Our diameter problem for families of sets was based on a mathematical abstraction (and a generalization) of the Hirsch Conjecture which asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Hirsch, in fact, made the conjecture also for graphs of unbounded polyhedra – namely the intersection of n closed halfspaces in R^d. But in the unbounded case, Klee and Walkup found a counterexample with diameter n-d+ [d/5]. The abstract problem we considered extends also to the unbounded case and  n-d+ [d/5] is the best known lower bound for the abstract case as well. It is not known if there is a polynomial (in terms of d and n) upper bound for the diameter of graphs of d-polytopes with n facets.

Hirsch’s conjecture was motivated by the simplex algorithm for linear programming.  Let us talk a little more about it: Linear programming is the problem of maximizing a linear objective function \phi(x)=b_1x_1+ b_2 x_2 \dots +b_dx_d subject to a system of n linear inequalities in the variables x_1,x_2,\dots,x_d.

 a_{11}x_1 + x_{12}x_2 + \dots + x_{1d}x_d \le c_1,

a_{21}x_1 + x_{22}x_2 + \dots + x_{2d}x_d \le c_2,

a_{n1}x_1 + x_{n2}x_2 + \dots + x_{nd}x_d \le c_n,

The set of solutions to the system of inequalities is a convex polyhedron. (If it is bounded it is a polytope.)  A linear objective function makes a graph of a polytope (or a polyhedron) into a digraph (directed graph). If you like graphs you would love digraphs, and if you like graphs of polytopes, you would like the digraphs associated with them.  

The geometric description of Dantzig’s simplex algorithm is as follows: the system of inequalities describes a convex d-dimensional polyhedron P. (This polyhedron is called the feasible polyhedron.) The maximum of \phi is attained at a face F of P. We start with an initial vertex (extreme point) v of the polyhedron and look at its neighbors in G(P). Unless v \in F there is a neighbor u of v that satisfies \phi(u) > \phi (v). When you find such a vertex move from v to u and repeat!

8. Abstract objective functions and unique sink orientation.

Let P be a simple d-polytope and let \phi be a linear objective function which is not constant on any edge of the polytope. Remember, the graph of P, G(P) is a d-regular graph. We can now direct every edge u,v from u to v if \phi (v) > \phi (u). Here are two important properties of this digraph.

(AC) It is acyclic! (no cycles)

(US’) It has a unique SINK, namely a unique vertex such that all edges containing it are directed towards it.

The unique sink property is in fact the property that enables the simplex algorithm to work!

When we consider a face of the polytope F and its own graph G(F) then again our linear objective function induces an orientation of the edges of G(F) which is acyclic and also has the unique sink property. Every subgraph of an acyclic graph is acyclic. But having the unique sink property for a graph does not imply it for a subgraph. We can now describe the general unique sink properties of digraphs of polytopes:

(US) For every face F of the polytope, the directed graph induced on the vertices of F has a unique sink.

A unique sink acyclic orientation of the graph of a polytope is an orientation of the edges of the graph which satisfies properties (AC) and (US). 

An abstract objective function of a d-polytope is an ordering < of the vertices of the polytope such that the directed graph obtained by directing an edge from u to v if  u<v is a unique sink acyclic orientation. (Of course, coming from an ordering the orientation is automatically acyclic.) 

Continue reading