Category Archives: Computer Science

What's wrong---and what's right---about quantum parallelism as an explanation for quantum speedup

Posted on by

I couldn't help crying "Nooo!!!!" on Twitter to the following statement by Pierre Pariente, "Strategic Analyst chez L’Atelier BNP Paribas," from a 2015 article "Quantum Computing Set to Revolutionize the Health Sector"

L’Atelier's more mathematically-inclined readers will recognise the general rule that with n qbits, a quantum computer may be in a quantum superposition of 2^n states and will thus possess the capacity to solve that number of problems simultaneously.

In the interest of not just being negative, I should explain what's wrong with this statement---and why it does capture something relevant to many examples of what most quantum computation theorists believe to be theoretical speed advantages of quantum algorithms over classical algorithms.  I'll give the short version first, and maybe in another post I'll explain a bit (groan) more.

What's wrong with quantum parallelism?

If you want, you can run a quantum version of a classical algorithm for solving some problem---say, computing a function on an n-bit long input string---on a superposition of all 2^n states representing different input strings.  This is often called "quantum parallelism".  If we consider computing the value of some function, F, on each input x to be "solving a different problem", then in some very weak sense we might think of this as "solving 2^n different problems simultaneously".  However, the drug designers, or radiotherapists, or whoever one is going to be selling one's quantum computers and software to, are presumably going to want to know the answers to the problems.  But you cannot read out of a quantum computer that has run such a "quantum parallel" computation  the answer to all of these problems (the value of the function on all inputs).  In fact, you can read out the answer to only one of the problems (the value, F(x), of F on a particular input x).  If you have run in superposition and you measure the register in which the algorithm writes the value F(x), you'll get the answer on a randomly drawn input (the famous randomness of quantum theory), and if you measure a part of the computer where the input string was stored, you'll also get the value of said randomly drawn input. There is absolutely no advantage here over just running the classical algorithm on a randomly chosen input.

What's right with quantum parallelism

So how can this quantum parallelism nevertheless be useful?  The reason for this is essentially the existence of many mutually incompatible observables in quantum theory (position and momentum being the most famous example of a pair of incompatible observables, though they are not the ones usually used in proposals for quantum computation).  In particular, quantum theory allows such a superposition state to be effectively (and often efficiently) measured in ways other than reading out the value of F and the input that gave rise to it---ways incompatible with that readout.  This can tell us certain things about the function F other than its values on specific inputs, and these things may even depend on its values on exponentially many inputs.  The incompatibility of these measurements with the one that reads out the input and the function value, implies that once the global information is obtained, the information about inputs and function values is no longer available---an example of the well-known fact that  "measurement disturbs the state" of a quantum system.

Why do we care?

Many problems of practical interest take this form:  we have a program (say, a classical circuit---from which we can always construct a quantum circuit) for computing a function F, but we want to know something about the function that we don't know how to just read off from the information we used to construct the circuit. For example, if F takes values in an ordered set (like the real numbers, to some precision) we might want to know its maximum value, and probably also an input on which it takes this maximum. (This application, "optimization", is mentioned in the article.)  Or, we might know because of the way the circuit for computing the function is constructed that it is periodic (we will need for the set of inputs to have some structure some that allows us to define periodicity, of course---maybe they are interpreted as binary notation for integers, for example), but we might not know---and might want to know---the period.  To oversimplify a bit, solving this problem is the key ingredient in Shor's algorithm for factoring large integers using quantum computation---the one that breaks currently used public-key cryptography protocols.  If we could compute and read out the values of the function on all inputs, of course we could figure out about anything we want about it---but since there are 2^n inputs, doing things this way is going to take exponential (in n) resources---e.g., 2^n calculations of the function.  To repeat, it is the fact that quantum computing allows such a superposition state to be effectively measured in ways other than reading out the value of F, that  nevertheless gives us potential access, after just one function evaluation, to a certain amount of information about "global" aspects of the function, like its period, that depend on many values.   We are still very limited as to how much information we can get about the function in one run of a "quantum parallel" function evaluation---certainly, it is only polynomially much, not the exponentially much one could get by reading out its value on all inputs.  But in some cases, we can get significant information about some global aspect of the function that we care about, with a number of quantum-parallel function evaluations that, if they were mere classical function evaluations, would leave us with the ability to get far less information, or even no information, about that global aspect of the function.  How significant this speedup is may depend on what global information we want to know about the function, and what we know about it  ahead of time.  If we know it is periodic, then in good cases, we can use polynomially many evaluations to get the period in situations where it's thought we'd need exponentially many classical evaluations.  This is the basis of the "near-exponential"  speedup of factoring by Shor's algorithm (it is not quite exponential, presumably because the best classical algorithm is not just to try to brute-force find the period that is found in the quantum algorithm, but is more sophisticated).   For relatively unstructured optimization problems, quantum algorithms usually make use of Grover's algorithm, which, again, does use quantum parallelism, and can find the optimum to high precision with roughly the *square root* of the number of function evaluations needed classically.  If the classical algorithm needs (some constant times) 2^n evaluations, in other words, the quantum one will need roughly (some constant times) 2^{n/2}---still exponential, though with half the exponent; an advantage which could still be useful if the large constant cost factor that comes from doing quantum operations instead of classical ones does not swamp it.

Quantum algorithms beyond quantum-parallelism

There are of course other scenarios in which quantum computing may be useful, that are not well described as "finding out unknown properties of a function by running a circuit for it"---especially those where the problem itself comes from quantum physics, or happens to have a mathematical structure similar to that of quantum physics.   Typically these have the property that one is still "finding out unknown properties of a quantum circuit by running it", but the circuit is not necessarily a quantum version of a classical function evaluation, but rather represents some mathematical structure, or physical evolution, that is well-described by a quantum circuit.  The most obvious example is of course the evolution of some quantum physical system!  Some of these kinds of problems---like quantum chemistry applications---are among those potentially relevant to the health applications that are the topic of the BNP article.

ITFP, Perimeter: selective guide to talks. #1: Brukner on quantum theory with indefinite causal order

Posted on by

Excellent conference the week before last at Perimeter Institute: Information Theoretic Foundations for Physics.  The talks are online; herewith a selection of some of my favorites, heavily biased towards ideas new and particularly interesting to me (so some excellent ones that might be of more interest to you may be left off the list!).  Some of what would have been possibly of most interest and most novel to me happened on Weds., when the topic was spacetime physics and information, and I had to skip the day to work on a grant proposal.  I'll have to watch those online sometime.  This was going to be one post with thumbnail sketches/reviews of each talk, but as usual I can't help running on, so it may be one post per talk.

All talks available here, so you can pick and choose. Here's #1 (order is roughly temporal, not any kind of ranking...):

Caslav Brukner kicked off with some interesting work on physical theories in with indefinite causal structure.  Normally in formulating theories in an "operational" setting (in which we care primarily about the probabilities of physical processes that occur as part of a complete compatible set of possible processes) we assume a definite causal (partial) ordering, so that one process may happen "before" or "after" another, or "neither before nor after".  The formulation is "operational" in that an experimenter or other agent may decide upon, or at least influence, which set of processes, out of possible compatible sets, the actual process will be drawn, and then nature decides (but with certain probabilities for each possible process, that form part of our theory), which one actually happens.  So for instance, the experimenter decides to perform a Stern-Gerlach experiment with a particular orientation X of the magnets; then the possible processes are, roughly, "the atom was deflected in the X direction by an angle theta," for various angles theta.  Choose a different orientation, Y, for your apparatus, you choose a different set of possible compatible processes.  ("The atom was deflected in the Y direction by an angle theta.")  Then we assume that if one set of compatible processes happens after another, an agent's choice of which complete set of processes is realized later, can't influence the probabilities of processes occuring in an earlier set.  "No signalling from the future", I like to call this; in formalized operational theories it is sometimes called the "Pavia causality axiom".   Signaling from the past to the future is fine, of course.  If two complete  sets of processes are incomparable with respect to causal order ("spacelike-separated"), the no-signalling constraint operates both ways:  neither Alice's choice of which compatible set is realized, nor Bob's, can influence the probabilities of processes occuring at the other agent's site.   (If it could, that would allow nearly-instantaneous signaling between spatially separated sites---a highly implausible phenomenon only possible in preposterous theories such as the Bohmian version of quantum theory with "quantum disequilibrium", and Newtonian gravity. ) Anyway, Brukner looks at theories that are close to quantum, but in which this assumption doesn't necessarily apply: the probabilities exhibit "indeterminate causal structure".  Since the theories are close to quantum, they can be interpreted as allowing "superpositions of different causal structures", which is just the sort of thing you might think you'd run into in, say, theories combining features of quantum physics with features of general relativistic spacetime physics.  As Caslav points out, since in general relativity the causal structure is influenced by the distribution of mass and energy, you might hope to realize such indefinite causal structure by creating a quantum superposition of states in which a mass is in one place, versus being in another.  (There are people who think that at some point---some combinations of spatial scales (separation of the areas in which the mass is located) and mass scales (amount of mass to be separated in "coherent" superposition)) the possibility of such superpositions breaks down.  Experimentalists at Vienna (where Caslav---a theorist, but one who likes to work with experimenters to suggest experiments---is on the faculty) have created what are probably the most significant such superpositions.)

Situations with a superposition of causal orders seem to be exhibit some computational advantages over standard causally-ordered quantum computation, like being able to tell in fewer queries (one?) whether a pair of unitaries commutes or anticommutes.  Not sure whose result that was (Giulio Chiribella and others?), but Caslav presents some more recent results on query complexity in this model, extending the initial results.  I am generally wary about results on computation in theories with causal anomalies.  The stuff on query complexity with closed timelike curves, e.g. by Dave Bacon and by  Scott Aaronson and John Watrous has seemed uncompelling---not the correctness of the mathematical results, but rather the physical relevance of the definition of computation---to me for reasons similar to those given by Bennett, Leung, Smith and Smolin.  But I tend to suspect that Caslav and the others who have done these query results, use a more physically compelling framework because they are well versed in the convex operational or "general probabilistic theories" framework which aims to make the probabilistic behavior of processes consistent under convex combination ("mixture", i.e. roughly speaking letting somebody flip coins to decide which input to present your device with).  Inconsistency with respect to such mixing is part of the Bennett/Leung/Smolin/Smith objection to the CTC complexity classes as originally defined.

[Update:  This article at Physics.org quotes an interview with Scott Aaronson responding to the Bennett et. al. objections.  Reasonably enough, he doesn't think the question of what a physically relevant definition of CTC computing is has been settled.  When I try to think about this issue sometimes I wonder if the thorny philosophical question of whether we court inconsistency by trying to combine intervention ("free choice of inputs") in a physical theory is rearing its head.  As often with posts here, I'm reminding myself to revisit the issue at some point... and think harder.]

My short review of David Deutsch's "The Beginning of Infinity" in Physics Today

Posted on by

Here is a link to my short review of David Deutsch's book The Beginning of Infinity, in Physics Today, the monthly magazine for members of the American Physical Society.  I had much more to say about the book, which is particularly ill-suited to a short-format review like those in Physics Today.  (The title is suggestive; and a reasonable alternative would have been "Life, the Universe, and Everything.")   It was an interesting exercise to boil it down to this length, which was already longer than their ideal.  I may say some of it in a blog post later.

It was also interesting to have such extensive input from editors.  Mostly this improved things, but in a couple of cases (not helped by my internet failing just as the for-publication version had been produced) the result was not good.  In particular, the beginning of the second-to-last paragraph, which reads "For some of Deutsch’s concerns, prematurity is irrelevant. But fallibilism undermines some of his claims ... " is not as I'd wanted.  I'd had "this" in place of "prematurity" and "it" in place of "fallibilism".  I'd wanted, in both cases, to refer in general to the immediately preceding discussion, more broadly than just to "prematurity" in one case and "fallibilism" in the other.  It seems the editors felt uncomfortable with a pronoun whose antecedent was not extremely specific.  I'd have to go back to notes to see what I ultimately agreed to, but definitely not plain "prematurity".

One other thing I should perhaps point out is that when I wrote:

Deutsch’s view that objective correctness is possible in areas outside science is appealing. And his suggestion that Popperian explanation underwrites that possibility is intriguing, but may overemphasize the importance of explanations as opposed to other exercises of reason. A broader, more balanced perspective may be found in the writings of Roger Scruton, Thomas Nagel, and others.

I was referring to a broader perspective on the role of reason in arriving at objectively correct views in areas outside science. "More balanced" was another editorial addition, in this case one that I acquiesced in, but perhaps I should not have as some of its possible connotations are more negative than I intended.  "Appealing," though not an editorial edition, is somewhat off from what I intended.  I wanted also to include suggestion of "probably correct" since something can be appealing but wrong, but couldn't find the right word.  I shortened this discussion for reasons of space, but I had initially cited Scruton specifically for aesthetics, and recommended his "On Beauty", "Art and the Imagination", and "The Aesthetics of Architecture".  I haven't read much of his work on politics (he is a conservative, although from what I have read a relatively sensible one at the philosophical level) nor his "Sexual Desire", so don't mean to endorse them.  Likewise I had initially recommended specifically Nagel's "The View from Nowhere" and "The Last Word", and was not aware of his recent "Mind and Cosmos"; I emphatically did not mean to endorse his skepticism, in that book, about evolutionary explanations of the origins of life and mind, although I do think there is much of interest in that book, and some (but certainly not all!) of the criticism of it that I've seen on the web is misguided.  I am much more in sympathy with Deutsch's views on reductionism than with Nagel's:  both are skeptical about the prospects for a thoroughoing reduction of mind, reason, and consciousness to physical terms, but Nagel, bafflingly, seems to think that an evolutionary explanation of such phenomena is tantamount to such physical reductionism.  Deutsch seems to me more sophisticated about the nature of actual science, and how non-reductionist many scientific explanations are, and about how that can nevertheless be compatible with physical law.  I should say, though, that I am less sympathetic than Deutsch is to accounts of mind and consciousness as being essentially a computer running a certain kind of program.  I view embodiment, interaction with a sufficiently rich environment, and probably a difficulty in disentangling "hardware" and "software" (perhaps related to Douglas Hofstadter's notion of "strange loops") as likely to be crucial elements of an understanding of mind and consciousness.  Of course it may be that with a sufficiently loose notion of "kind of computer program" and "kind of input" some of this could be understood in the computational terms Deutsch seeks.

No new enlightenment: A critique of "quantum reason"

Posted on by

I have a lot of respect for Scientific American contributing physics editor George Musser's willingness to solicit and publish articles on some fairly speculative and, especially, foundational, topics whether in string theory, cosmology, the foundations of quantum theory, quantum gravity, or quantum information.  I've enjoyed and learned from these articles even when I haven't agreed with them.  (OK, I haven't enjoyed all of them of course... a few have gotten under my skin.)  I've met George myself, at the most recent FQXi conference; he's a great guy and was very interested in hearing, both from me and from others, about cutting-edge research.  I also have a lot of respect for his willingness to dive in to a fairly speculative area and write an article himself, as he has done with "A New Enlightenment" in the November 2012 Scientific American (previewed here).  So although I'm about to critique some of the content of that article fairly strongly, I hope it won't be taken as mean-spirited.  The issues raised are very interesting, and I think we can learn a lot by thinking about them; I certainly have.

The article covers a fairly wide range of topics, and for now I'm just going to cover the main points that I, so far, feel compelled to make about the article.  I may address further points later; in any case, I'll probably do some more detailed posts, maybe including formal proofs, on some of these issues.

The basic organizing theme of the article is that quantum processes, or quantum ideas, can be applied to situations which social scientists usually model as involving the interactions of "rational agents"...or perhaps, as they sometimes observe, agents that are somewhat rational and somewhat irrational.  The claim, or hope, seems to be that in some cases we can either get better results by substituting quantum processes (for instance, "quantum games", or "quantum voting rules") for classical ones, or perhaps better explain behavior that seems irrational.  In the latter case, in this article, quantum theory seems to be being used more as a metaphor for human behavior than as a model of a physical process underlying it.  It isn't clear to me whether we're supposed to view this as an explanation of irrationality, or in some cases as the introduction of a "better", quantum, notion of rationality.  However, the main point of this post is to address specifics, so here are four main points; the last one is not quantum, just a point of classical political science.

 

(1) Quantum games.  There are many points to make on this topic.  Probably most important is this one: quantum theory does not resolve the Prisoner's Dilemma.  Under the definitions I've seen of "quantum version of a classical game", the quantum version is also a classical game, just a different one.  Typically the strategy space is much bigger.  Somewhere in the strategy space, typically as a basis for a complex vector space ("quantum state space") of strategies, or as a commuting ("classical") subset of the possible set of "quantum actions" (often unitary transformations, say, that the players can apply to physical systems that are part of the game-playing apparatus), one can set things up so one can compare the expected payoff of the solution, under various solution concepts such as Nash equilibrium, for the classical game and its "quantum version", and it may be that the quantum version has a better result for all players, using the same solution concept.  This was so for Eisert, Lewenstein, and Wilkens' (ELW for short) quantum version of Prisoner's Dilemma.  But this does not mean (nor, in their article, did ELW claim it did) that quantum theory "solves the Prisoner's Dilemma", although I suspect when they set out on their research, they might have had hope that it could.  It doesn't because the prisoners can't transform their situation into quantum prisoners dilemma; to play that game, whether by quantum or classical means, would require the jailer to do something differently.  ELW's quantum prisoner's dilemma involves starting with an entangled state of two qubits.  The state space consists of the unit Euclidean norm sphere in a 4-dimensional complex vector space (equipped with Euclidean inner product); it has a distinguished orthonormal basis which is a product of two local "classical bases", each of which is labeled by the two actions available to the relevant player in the classical game.  However the quantum game consists of each player choosing a unitary operator to perform on their local state.  Payoff is determined---and here is where the jailer must be complicit---by performing a certain two-qubit unitary---one which does not factor as a product of local unitaries---and then measuring in the "classical product basis", with payoffs given by the classical payoff corresponding to the label of the basis vector corresponding to the result.  Now, Musser does say that "Quantum physics does not erase the original paradoxes or provide a practical system for decision making unless public officials are willing to let people carry entangled particles into the voting booth or the police interrogation room."  But the situation is worse than that.  Even if prisoners could smuggle in the entangled particles (and in some realizations of prisoners' dilemma in settings other than systems of detention, the players will have a fairly easy time supplying themselves with such entangled pairs, if quantum technology is feasible at all), they won't help unless the rest of the world, implementing the game, implements the desired game, i.e. unless the mechanism producing the payoffs doesn't just measure in a product basis, but implements the desired game by measuring in an entangled basis.  Even more importantly, in many real-world games, the variables being measured are already highly decohered; to ensure that they are quantum coherent the whole situation has to be rejiggered.  So even if you didn't need the jailer to make an entangled measurement---if the measurement was just his independently asking each one of you some question---if all you needed was to entangle your answers---you'd have to either entangle your entire selves, or covertly measure your particle and then repeat the answer to the jailer.  But in the latter case, you're not playing the game where the payoff is necessarily based on the measurement result: you could decide to say something different from the measurement result.  And that would have to be included in the strategy set.

There are still potential applications:  if we are explicitly designing games as mechanisms for implementing some social decision procedure, then we could decide to implement a quantum version (according to some particular "quantization scheme") of a classical game.  Of course, as I've pointed out, and as ELW do in their paper, that's just another classical game.  But as ELW note, it is possible---in a setting where quantum operations (quantum computer "flops") aren't too much more expensive than their classical counterparts---that playing the game by quantum means might use less resources than playing it by simulating it classically.  In a mechanism design problem that is supposed to scale to a large number of players, it even seems possible that the classical implementation could scale so badly with the number of players as to become infeasible, while the quantum one could remain efficient.  For this reason, mechanism design for preference revelation as part of a public goods provision scheme, for instance, might be a good place to look for applications of quantum prisoners-dilemma like games.  (I would not be surprised if this has been investigated already.)

Another possible place where quantum implementations might have an advantage is in situations where one does not fully trust the referee who is implementing the mechanism.  It is possible that quantum theory might enable the referee to provide better assurances to the players that he/she has actually implemented the stated game.  In the usual formulation of game theory, the players know the game, and this is not an issue.  But it is not necessarily irrelevant in real-world mechanism design, even if it might not fit strictly into some definitions of game theory.  I don't have a strong intuition one way or the other as to whether or not this actually works but I guess it's been looked into.

(2) "Quantum democracy".  The part of the quote, in the previous item, about taking entangled particles into the voting booth, alludes to this topic.  Gavriel Segre has a 2008 arxiv preprint entitled "Quantum democracy is possible" in which he seems to be suggesting that quantum theory can help us the difficulties that Arrow's Theorem supposedly shows exist with democracy.  I will go into this in much more detail in another post.  But briefly, if we consider a finite set A of "alternatives", like candidates to fill a single position, or mutually exclusive policies to be implemented, and a finite set I of "individuals" who will "vote" on them by listing them in the order they prefer them, a "social choice rule" or "voting rule" is a function that, for every "preference profile", i.e. every possible indexed set of preference orderings (indexed by the set of individuals), returns a preference ordering, called the "social preference ordering", over the alternatives.  The idea is that then whatever subset of alternatives is feasible, society should choose the one mostly highly ranked by the social preference ordering,  from among those alternatives that are feasible.  Arrow showed that if we impose the seemingly reasonable requirements that if everyone prefers x to y, society should prefer x to y ("unanimity") and that whether or not society prefers x to y should be affected only by the information of which individuals prefer x to y, and not by othe aspects of individuals' preference orderings ("independence of irrelevant alternatives", "IIA"), the only possible voting rules are the ones such that, for some individual i called the "dictator" for the rule, the rule is that that individual's preferences are the social preferences.  If you define a democracy as a voting rule that satisfies the requirements of unanimity and IIA and that is not dictatorial, then "democracy is impossible".  Of course this is an unacceptably thin concept of individual and of democracy.  But anyway, there's the theorem; it definitely tells you something about the limitations of voting schemes, or, in a slighlty different interpretation, of the impossibility of forming a reasonable idea of what is a good social choice, if all that we can take into account in making the choice is a potentially arbitrary set of individuals' orderings over the possible alternatives.

Arrow's theorem tends to have two closely related interpretations:  as a mechanism for combining actual individual preferences to obtain social preferences that depend in desirable ways on individual ones, or as a mechanism for combining formal preference orderings stated by individuals, into a social preference ordering.  Again this is supposed to have desirable properties, and those properties are usually motivated by the supposition that the stated formal preference orderings are the individuals' actual preferences, although I suppose in a voting situation one might come up with other motivations.  But even if those are the motivations, in the voting interpretation, the stated orderings are somewhat like strategies in a game, and need not coincide with agents' actual preference orderings if there are strategic advantages to be had by letting these two diverge.

What could a quantum mitigation of the issues raised by Arrow's theorem---on either interpretation---mean?  We must be modifying some concept in the theorem... that of an individual's preference ordering, or voting strategy, or that of alternative, or---although this seems less promising---that of individual---and arguing that somehow that gets us around the problems posed by the theorem.  None of this seems very promising, for reasons I'll get around to in my next post.  The main point is that if the idea is similar to the --- as we've seen, dubious --- idea that superposing strategies can help in quantum games, it doesn't seem to help with interpretations where the individual preference ordering is their actual preference ordering.  How are we to superpose those?  Superposing alternatives seems like it could have applications in a many-worlds type interpretation of quantum theory, where all alternatives are superpositions to begin with, but as far as I can see, Segre's formalism is not about that.  It actually seems to be more about superpositions of individuals, but one of the big motivational problems with Segre's paper is that what he "quantizes" is not the desired Arrow properties of unanimity, independence of irrelevant alternatives, and nondictatoriality, but something else that can be used as an interesting intermediate step in proving Arrow's theorem.  However, there are bigger problems than motivation:  Segre's main theorem, his IV.4, is very weak, and actually does not differentiate between quantum and classical situations.  As I discuss in more detail below, it looks like for the quantum logics of most interest for standard quantum theory, namely the projection lattices of of von Neumann algebras, the dividing line between ones having what Segre would call a "democracy", a certain generalization of a voting rule satisfying Arrow's criteria, and ones that don't (i.e. that have an "Arrow-like theorem") is not commutativity versus noncommutativity of the algebra (ie., classicality versus quantumness), but just infinite-dimensionality versus finite-dimensionality, which was already understood for the classical case.  So quantum adds nothing.  In a later post, I will go through (or post a .pdf document) all the formalities, but here are the basics.

Arrow's Theorem can be proved by defining a set S of individuals to be decisive if for every pair x,y of alternatives, whenever everyone in S prefers x to y, and everyone not in x prefers y to x, society prefers x to y.  Then one shows that the set of decisive sets is an ultrafilter on the set of individuals.  What's an ultrafilter?  Well, lets define it for an arbitrary lattice.  The set, often called P(I), of subsets of any set I, is a lattice (the relevant ordering is subset inclusion, the defined meet and join are intersection and union).   A filter---not yet ultra---in a lattice is a subset of the lattice that is upward-closed, and meet-closed.  That is, to say that F is a filter is to say that  if x is in F, and y is greater than or equal to x, then y is in F, and that if x and y are both in f, so is x meet y.  For P(I), this means that a filter has to include every superset of each set in the filter, and also the intersection of every pair of sets in the filter.  Then we say a filter is proper if it's not the whole lattice, and it's an ultrafilter if it's a maximal proper filter, i.e. it's not properly contained in any other filter (other than the whole lattice).  A filter is called principal if it's generated by a single element of the lattice:  i.e. if it's the smallest filter containing that element.  Equivalently, it's the set consisting of that element and everything above it.  So in the case of P(I), a principal filter consists of a given set, and all sets containing that set.

To prove Arrow's theorem using ultrafilters, one shows that unanimity and IIA imply that the set of decisive sets is an ultrafilter on P(I).  But it was already well known, and is easy to show, that all ultrafilters on the powerset of a finite set are principal, and are generated by singletons of I, that is, sets containing single elements of I.  So a social choice rule satisfying unanimity and IIA has a decisive set containing a single element i, and furthermore, all sets containing i are decisive.  In other words, if i favors x over y, it doesn't matter who else favors x over y and who opposes it: x is socially preferred to y.  In other words, the rule is dictatorial.  QED.

Note that it is crucial here that the set I is finite.  If you assume the axiom of choice (no pun intended ahead of time), then non-principal ultrafilters do exist in the lattice of subspaces of an infinite set, and the more abstract-minded people who have thought about Arrow's theorem and ultrafilters have indeed noticed that if you are willing to generalize Arrow's conditions to an infinite electorate, whatever that means, the theorem doesn't generalize to that situation.  The standard existence proof for a non-principal ultrafilter is to use the axiom of choice in the form of Zorn's lemma to establish that any proper filter is contained in a maximal one (i.e. an ultrafilter) and then take the set of subsets whose complement (in I) is finite, show it's a filter, and show it's extension to an ultrafilter is not principal.  Just for fun, we'll do this in a later post.  I wouldn't summarize the situation by saying "infinite democracies exist", though.  As a sidelight, some people don't like the fact that the existence proof is nonconstructive.

As I said, I'll give the details in a later post.  Here, we want to examine Segre's proposed generalization.  He defines a quantum democracy  to be a nonprincipal ultrafilter on the lattice of projections of an "operator-algebraically finite von Neumann algebra".  In the preprint there's no discussion of motivation, nor are there explicit generalizations of unanimity and IIA to corresponding quantum notions.  To figure out such a correspondence for Segre's setup we'd need to convince ourselves that social choice rules, or ones satisfying one or the other of Arrow's properties, are related one to one to their sets of decisive coalitions, and then relate properties of the rule (or the remaining property), to the decisive coalitions' forming an ultrafilter.  Nonprincipality is clearly supposed to correspond to nondictatorship.  But I won't try to tease out, and then critique, a full correspondence right now, if one even exists.

Instead, let's look at Segre's main point.  He defines a quantum logic as a non-Boolean orthomodular lattice.  He defines a quantum democracy as a non-principal ultrafilter in a quantum logic.  His main theorem, IV.4, as stated, is that the set of quantum democracies is non-empty.  Thus stated, of course, it can be proved by showing the existence of even one quantum logic that has a non-principal ultrafilter.  These do exist, so the theorem is true.

However, there is nothing distinctively quantum about this fact.  Here, it's relevant that Segre's Theorem IV.3 as stated is wrong.  He states (I paraphrase to clarify scope of some quantifiers) that L is an operator-algebraically finite orthomodular lattice all of whose ultrafilters are principal if, and only if, L is a classical logic (i.e. a Boolean lattice).  But this is false.  It's true that to get his theorem IV.4, he doesn't need this equivalence.  But what is a von Neumann algebra?  It's a *-algebra consisting of bounded operators on a Hilbert space, closed in the weak operator topology.  (Or something isomorphic in the relevant sense to one of these.) There are commutative and noncommutative ones.  And there are finite-dimensional ones and infinite-dimensional ones.  The finite-dimensional ones include:  (1) the algebra of all bounded operators on a finite-dimensional Hilbert space (under operator multiplication and complex conjugation), these are noncommutative for dimension > 1  (2) the algebra of complex functions on a finite set I (under pointwise multiplication and complex conjugation) and (3) finite products (or if you prefer the term, direct sums) of algebras of these types.  (Actually we could get away with just type (1) and finite products since the type (2) ones are just finite direct sums of one-dimensional instances of type (1).)   The projection lattices of the cases (2) are isomorphic to P(I) for I the finite set.  These are the projection lattices for which Arrow's theorem can be proved using the fact that they have no nonprincipal ultrafilters.  The cases (1) are their obvious quantum analogues.  And it is easy to show that in these cases, too, there are no nonprincipal ultrafilters.  Because the lattice of projections of a von Neumann algebra is complete, one can use  essentially the same proof as for the case of P(I) for finite I.  So for the obvious quantum analogues of the setups where Arrow's theorem is proven, the analogue of Arrow's theorem does hold, and Segre's "quantum democracies" do not exist.

Moreover, Alex Wilce pointed out to me in email that essentially the same proof as for P(I) with I infinite, gives the existence of a nonprincipal ultrafilter for any infinite-dimensional von Neumann algebra:  one takes the set of projections of cofinite rank (i.e. whose orthocomplementary projection has finite rank), shows it's a filter, extends it (using Zorn's lemma) to an ultrafilter, and shows that's not principal.  So (if the dividing line between finite-dimensional and infinite-dimensional von Neumann algebras is precisely that their lowest-dimensional faithful representations are on finite-dimensional Hilbert spaces, which seems quite likely) the dividing line between projection lattices of von Neumann algebras on which Segre-style "democracies" (nonprincipal ultrafilters) exist, is precisely that between finite and infinite dimension, and not that between commutativity and noncommutativity.  I.e. the existence or not of a generalized decision rule satisfying a generalization of the conjunction of Arrow's conditions has nothing to do with quantumness.  (Not that I think it would mean much for social choice theory or voting if it did.)

(3) I'll only say a little bit here about "quantum psychology".  Some supposedly paradoxical empirical facts are described at the end of the article.  When subjects playing Prisoner's Dilemma are told that the other player will snitch, they always (nearly always? there must be a few mistakes...) snitch.  When they are told that the other player will stay mum, they usually also fink, but sometimes (around 20% of the time---it is not stated whether this typical of a single individual in repeated trials, or a percentage of individuals in single trials) stay mum.  However, if they are not told what the other player will do, "about 40% of the time" they stay mum.  Emanuel Pothos and Jerome Busemeyr devised a "quantum model" that reproduced the result.  As described in Sci Am, Pothos interprets it in terms of destructive interference between (amplitudes associated with, presumably) the 100% probability of snitching when the other snitches and the 80% probability of snitching when they other does not that reduces the probability to 60% when they are not sure whether the other will snitch.  It is a model; they do not claim that quantum physics of the brain is responsible.  However, I think there is a better explanation, in terms of what Douglas Hofstadter called "superrationality", Nigel Howard called "metarationality", and I like to call a Kantian equilibrium concept, after the version of Kant's categorial imperative that urges you to act according to a maxim that you could will to be a universal law.  Simply put, it's the line of reasoning that says "the other guy is rational like me, so he'll do what I do.  What does one do if he believes that?  Well, if we both snitch, we're sunk.  If we both stay mum, we're in great shape.  So we'll stay mum."  Is that rational?  I dunno.  Kant might have argued it is.  But in any case, people do consider this argument, as well, presumably, as the one for the Nash equilibrium.  But in either of the cases where the person is told what the other will do, there is less role for the categorical imperative; one is being put more in the Nash frame of mind.  Now it is quite interesting that people still cooperate a fair amount of the time when they know the other person is staying mum; I think they are thinking of the other person's action as the outcome of the categorical imperative reasoning, and they feel some moral pressure to stay with the categorical imperative reasoning.  Whereas they are easily swayed to completely dump that reasoning in the case when told the other person snitched: the other has already betrayed the categorical imperative.  Still, it is a bit paradoxical that people are more likely to cooperate when they are not sure whether the other person is doing so;  I think the uncertainty makes the story that "he will do what I do" more vivid, and the tempting benefit of snitching when the other stays mum less vivid, because one doesn't know *for sure* that the other has stayed mum.  Whether that all fits into the "quantum metaphor" I don't know but it seems we can get quite a bit of potential understanding here without invoking.  Moreover there probably already exists data to help explore some of these ideas, namely about how the same individual behaves under the different certain and uncertain conditions, in anonymous trials guaranteed not to involve repetition with the same opponent.

Less relevant to quantum theory, but perhaps relevant in assessing how important voting paradoxes are in the real world, is an entirely non-quantum point:

(4)  A claim by Piergiorgio Odifreddi, that the 1976 US election is an example of Condorcet's paradox of cyclic pairwise majority voting, is prima facie highly implausible to anyone who lived through that election in the US.  The claim is that a majority would have favored, in two-candidate elections:

Carter over Ford (as in the actual election)

Ford over Reagan

Reagan over Carter

I strongly doubt that Reagan would have beat Carter in that election.  There is some question of what this counterfactual means, of course:  using polls conducted near the time of the election does not settle the issue of what would have happened in a full general-election campaign pitting Carter against Reagan.  In "Preference Cycles in American Elections", Electoral Studies 13: 50-57 (1994), as summarized in Democracy Defended by Gerry Mackie, political scientist Benjamin Radcliff analyzed electoral data and previous studies concerning the US Presidential elections from 1972 through 1984, and found no Condorcet cycles.  In 1976, the pairwise orderings he found for (hypothetical, in two of the cases) two-candidate elections were Carter > Ford, Ford > Reagan, and Carter > Reagan.  Transitivity is satisfied; no cycle.  Obviously, as I've already discussed, there are issues of methodology, and how to analyze a counterfactual concerning a general election.  More on this, perhaps, after I've tracked down Odifreddi's article.  Odifreddi is in the Sci Am article because an article by him inspired Gavriel Segre to try to show that such problems with social choice mechanisms like voting might be absent in a quantum setting.

Odifreddi is cited by Musser as pointing out that democracies usually avoid Condorcet paradoxes because voters tend to line up on an ideological spectrum---I'm just sceptical until I see more evidence, that that was not the case also in 1976 in the US.  I have some doubt also about the claim that Condorcet cycles are the cause of democracy "becoming completely dysfunctional" in "politically unsettled times", or indeed that it does become completely dysfunctional in such times.  But I must remember that Odifreddi is from the land of Berlusconi.  But then again, I doubt cycles are the main issue with him...

Claimed proof of P not equal to NP by Vinay Deolalikar is being taken seriously

Posted on by

Via Richard Lipton, news that HP research scientist Vinay Deolalikar has put online a 102 page draft of a paper purporting to prove that P is not equal to NP.  (Follow the link to Deolalikar's page, and the paper is the first one linked under "Selected Publications".)  It is being taken seriously by serious people  (like Lipton)--- in the sense that they are trying to understand it and understand whether or not it is correct.   The length, of course, increases the likelihood of a so-far unspotted error.  Lipton thinks Deolalikar's use of finite model theory is an interesting and promising twist.  I have only just downloaded the paper, and am not a complexity theory expert, but what leaps out at me from the abstract is that it involves graphical models for sets of interacting random variables, an area that interests me.  Not that surprising, I guess, as lots of difficult problems---as well as ones that are easy but perhaps not obviously so, because of structure described by a graphical model of the dependencies between variables---are naturally described in graphical terms, and the relation between graphical models and complexity is a well-studied---though mostly relatively recently studied---topic.  I can no longer find the link to the online draft of Marc Mezard and Andrea Montanari's book on the subject (and its relations to physics and coding theory), perhaps because it's been published.  [Correction:  it's still online here.   Thanks to commenter Kristal Cantwell for the link.]  One key notion in such models is conditional independence---independence of two subsets of the random variables in question, when conditioned on a third set.  A really nice paper on a quantum notion of conditional independence, relating it to the equality conditions for the strong subadditivity inequality for quantum entropy, is by Hayden, Jozsa, Petz, and Winter.  Matt Leifer and David Poulin, and others, have described quantum graphical models.

You can bet that if Deolalikar's proof looks good, a slew of people will be applying the research strategy I like to call the "quantization functor" to it.

For those for whom P and NP are not their bread and butter, to give you an idea of how big this would be: I just goofed by telling my wife that if this pans out, it will be one of the most important results of twentieth century mathematics.  Well, it would have been if done in the twentieth century.  But I'll say more: although we're only 10 years in, I think it will be one of the most important results of twenty-first century mathematics.  I haven't said what it really means but that's what Wikipedia is for.

I should point out that Scott Aaronson is dubious, though not based on close perusal of the proof.  He has pledged to personally supplement the million dollars the Clay Mathematics Institute will pay Deolalikar if the proof is correct, with two hundred grand of his own.