Skip to content

Doubling up

by Michael Nielsen on August 20, 2004

As luck would have it, I submitted two papers to the quant-ph preprint archive today. They should both show up in a day or two. Both contain what I unabashedly think is some pretty neat stuff, so I’ll describe them here.

The first (joint work with Chris Dawson, Henry Haselgrove, Andrew Hines, Duncan Mortimer, and Tobias Osborne) paper relates quantum computing to something that, on the surface, you’d think had absolutely nothing to do with quantum computing: counting solutions to sets of polynomial equations.

In particular, we show that the problem of determining the output of a quantum computation is actually equivalent to the problem of being able to estimate the number of solutions to certain sets of polynomial equations, which we explicitly construct.

This is really quite odd. After all, it is believed pretty likely that quantum computers can be used to simulate any physical system. If you believe this, then what this result tells you is that simulating nature can be boiled down to counting solutions to polynomial equations.

What the heck does the simulation of physical systems have to do with counting solutions to polynomial equations? A priori, you wouldn’t think they’d be all that related. Yet the two problems turn out to be the same, in some sense. I find this really quite remarkable.

I should say, by the way, that other people have shown some related results in the past. I won’t give an account of that history here, though, as we have a detailed discussion in the paper, and I won’t do it justice in this small space.

The second paper (joint with Denes Petz, who has been visiting us at UQ), is a short expository note. It’s a simple elementary account of what may be just about the most important result in quantum information theory – the strong subadditivity inequality for entropy, first proved by Lieb and Ruskai in 1973. Almost everything we know about entropy comes from this inequality.

In the 1980s Denes found a simple (and, I think, extremely beautiful) proof of this result. Our note gives an account of this proof that is (a) short; (b) easy-to-understand (we assume only basic linear algebra and quantum mechanics); and (c) where you can learn something interesting at pretty much every step, if you pay attention. That’s the kind of proof I love to read, myself, which is why I’m so excited about this note!

From → General

12 Comments
  1. If high-fidelity simulations of physical systems seem likely to you, what do you feel about the conclusions of Bostrom’s Simulation Argument?
    ( http://www.simulation-argument.com/ )

    When I first read the argument I disagreed and thought it was silly… however, I realized the *reasons* I disagreed didn’t make sense. I guess post-modernism is good for something, because it helped lead me to accept the overall idea in the paper.

  2. I haven’t read it. I read one of Bostrom’s essays years ago (on the Doomsday Argument), and didn’t get much out of it. Given this prior experience, I’m not sure I want to invest the time necessary to read a long article by the same author. Life’s short, and there are many other things worth reading and doing.

  3. Well, it basically Bostrom says that, in the future, it will be incredibly cheap to simulate the experiences of a human brain. Thus, most human brain experiences in existence will overwhelmingly be simulations. Therefore, one of three things is possible: (1) humans never advance to making cheap simulations; (2) humans decide not to run simulations; or (3) it is ~90% likely that we are in a simulation right now.

  4. DavidM permalink

    Most real numbers are not integers. Should we conclude that it is ~90% likely that 2 is not an integer?

  5. DavidM, your example fails to be the same. Properly worded, it would be an understatement: “Most real numbers are not integers. r is a number. It is more than 90% likely that r is not an integer.”

    Here, it’s *way* more than likely, almost infinitely likely, that r is not an integer. You cannot simply choose “2” and say that’s that.

    The point is, any given human brain experience is most likely a simulation. (Or, not taking the main conclusion, then you must believe other startling ideas.)

  6. I have an oversimplified view of the world, but is the following relevant?

    Simulating a [quantum] system, involves, solving the Schrodinger’s equation, which is more or less, diagnoalizing the Hamiltonian “matrix” [no time-dependence, one can always enlarge the system], and the diagonalization corresponds to finding the roots of the characteristic equation, the real roots for a Hermitian matrix. Now as long as one knows how many roots an equation has [over the field R], finding them is just a matter of “searching” an interval, given the required precision. Or maybe this last piece is not as simple as I thought?

  7. Michael Nielsen permalink

    Kaveh: What we prove in the paper is that if U is a quantum computation, then transition elements like can be expressed (up to a known constant ofproportionality) as the difference of two numbers, each of which is the number of solutions to some specified set of polynomial equations over the finite field Z_2.

    Now, as you say, the problem of diagonalizing a unitary matrix or Hamiltonian is not entirely dissimilar. However, doing so will require solving exponentially many different equations, instead of just two,as we require.

  8. Michael Nielsen permalink

    For reasons I don’t understand, the last post omitted an expression for transition elements: \langle 0| U|0\rangle. I hope that came through.

    (In general, my net access is pretty flaky at the moment.)

  9. Thanks for the reply. The problem with your left and right brakets is that HTML confuses them. Use ampersand followed by “gt;” for “>” and ampersand followed by “lt;” for “<“.

  10. mitch permalink

    The point is, any given human brain experience is most likely a simulation. (Or, not taking the main conclusion, then you must believe other startling ideas.)

    This was the argument:

    in the future, it will be incredibly cheap to simulate the experiences of a human brain. Thus, most human brain experiences in existence will overwhelmingly be simulations. Therefore, one of three things is possible: (1) humans never advance to making cheap simulations; (2) humans decide not to run simulations; or (3) it is ~90% likely that we are in a simulation right now.

    Or, it could be that posthumans aren’t very interested in mere human simulations. Or, that these future simulations aren’t conscious simulations. Neither of which is a startling idea.

  11. mitch permalink

    “What the heck does the simulation of physical systems have to do with counting solutions to polynomial equations?”

    What doesn’t have to do with counting solutions to polynomial equations?

  12. Macneil permalink

    “””Or, it could be that posthumans aren’t very interested in mere human simulations. Or, that these future simulations aren’t conscious simulations. Neither of which is a startling idea.”””

    Well, not startling to you, but it is to others. I can’t really argue against what you do or do not find startling now, can I? The idea may be disturbing, but you should attack it for the right reasons.

    BTW, no where did I say they had to be posthuman.

Comments are closed.