Physics
ComputerScience,1970-2008-Computer Science-2004.jsonl.gz.gz
Computer Science
b35a1c05ebb2e27d0b143680e2297c2625f45031
Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices

This paper initiates the study of hidden variables from the discrete, abstract perspective of quantum computing. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list seven axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we construct a new hidden-variable theory that is both robust to small perturbations and indifferent to the identity operation, by exploiting an unexpected connection between unitary matrices and network flows. We also analyze previous hidden-variable theories of Dieks and Schrodinger in terms of our axioms. In a companion paper, we will show that actually sampling the history of a hidden variable under reasonable axioms is at least as hard as solving the Graph Isomorphism problem; and indeed is probably intractable even for quantum computers.


Introduction
Quantum mechanics lets us calculate the probability that (say) an electron will be found in an excited state if measured at a particular time. But it is silent about multiple-time or transition probabilities: that is, what is the probability that the electron will be in an excited state at time t 1 , given that it was in its ground state at an earlier time t 0 ? The usual response is that this question is meaningless, unless of course the electron was measured (or otherwise known with probability 1) to be in its ground state at t 0 . A different response-pursued by Schrödinger [22], Bohm [5], Bell [3], Nelson [19], Dieks [10], and others-treats the question as provisionally meaningful, and then investigates how one might answer it mathematically. Specific attempts at answers are called "hidden-variable theories." The appeal of hidden-variable theories is that they provide one possible solution to the measurement problem. For they allow us to apply unitary quantum mechanics to the entire universe (including ourselves), yet still discuss the probability of a future observation conditioned on our current observations. Furthermore, they let us do so without making any assumptions about decoherence or the nature of observers. For example, even if an observer were placed in coherent superposition, that observer would still have a sequence of definite experiences, and the probability of any such sequence could be calculated.
This paper initiates the study of hidden variables from a quantum computing perspective. We restrict our attention to the simplest possible setting: that of discrete time, a finite-dimensional Hilbert space, and a fixed orthogonal basis. Within this setting, we reformulate known hiddenvariable theories due to Dieks [10] and Schrödinger [22], and also introduce a new theory based on network flows. However, our main contribution is the axiomatic approach that we use. We propose seven axioms for hidden-variable theories in our setting, and then compare theories against each other based on which of the axioms they satisfy. A central question in this approach is which subsets of axioms can be satisfied simultaneously.
In a companion paper [1], we will make the connection to quantum computing explicit, by proving that under any hidden-variable theory that satisfies three reasonable axioms (called symmetry, indifference, and robustness), the ability to examine one's entire "history" through a quantum system would entail the ability to solve the Graph Isomorphism problem in polynomial time. What makes this result surprising is that, in the so-called oracle or black-box model, sampling histories would not entail the ability to solve NP-complete problems in polynomial time. We thus obtain the first good example of a computational model that appears "slightly" more powerful than the usual quantum computing model. This paper lays the groundwork for the computational results of [1], in particular by showing that there exists a hidden-variable theory satisfying the symmetry, indifference, and robustness axioms.
The paper is organized as follows. Section 1.1 formally defines hidden-variable theories in our sense; then Section 1.2 contrasts these theories with related ideas such as Bohmian mechanics and modal interpretations. Section 1.3 addresses the most common objections to our approach: for example, that the implicit dependence on a fixed basis is unacceptable.
In Section 2, we introduce seven possible axioms for hidden-variable theories. These are symmetry under permutation of basis states; indifference to the identity operation; robustness to small perturbations; "block robustness," a weaker version of robustness; commutativity with respect to spacelike-separated unitaries; commutativity for the special case of product states; and invariance under decomposition of mixed states into pure states. Ideally, a theory would satisfy all of these axioms. However, we show in Section 3 that no theory satisfies both indifference and commutativity; no theory satisfies both indifference and a stronger version of robustness; no theory satisfies indifference, robustness, and decomposition invariance; and no theory satisfies a stronger version of decomposition invariance. The proofs of two of these results use the same geometric facts that underlie the Bell inequalities.
In Section 4 we shift from negative to positive results. Section 4.1 presents a hidden-variable theory called the flow theory or FT , which is based on the Max-Flow-Min-Cut theorem from combinatorial optimization. The idea is to define a network of "pipes" from basis states at an initial time to basis states at a final time, and then route as much probability mass as possible through these pipes. The capacity of each pipe depends on the corresponding entry of the unitary acting from the initial to final time. To find the probability of transitioning from basis state |i to basis state |j , we then determine how much of the flow originating at |i is routed along the pipe to |j . Our main results are that FT is well-defined and that it is robust to small perturbations. Since FT trivially satisfies the indifference axiom, this implies that the indifference and robustness axioms can be satisfied simultaneously, which was not at all obvious a priori. The flow theory also satisfies symmetry, but not product commutativity, scalar invariance, or decomposition invariance. Section 4.2 presents a second theory that we call the Schrödinger theory or ST , since it is based on a pair of integral equations introduced in a 1931 paper of Schrödinger [22]. Schrödinger conjectured, but was unable to prove, the existence and uniqueness of a solution to these equations; the problem was not settled until the work of Nagasawa [18] in the 1980's. In our discrete setting the problem is simpler, and we give a self-contained proof of existence using a matrix scaling technique due to Sinkhorn [23]. The idea is as follows: we want to convert a unitary matrix that maps one quantum state to another, into a nonnegative matrix whose i th column sums to the initial probability of basis state |i , and whose j th row sums to the final probability of basis state |j . To do so, we first replace each entry of the unitary matrix by its absolute value, then normalize each column to sum to the desired initial probability, then normalize each row to sum to the desired final probability. But then the columns are no longer normalized correctly, so we normalize them again, then normalize the rows again, and so on. We show that this iterative process converges, from which it follows that ST is well-defined. We also show that ST satisfies the symmetry, indifference, and product commutativity axioms; and violates the decomposition invariance axiom. We conjecture that ST satisfies the robustness axiom; proving that conjecture is the main open problem of the paper. We conclude in Section 5.

Hidden-Variable Theories
Suppose we have an N × N unitary matrix U , acting on a state where |1 , . . . , |N is a standard orthogonal basis. Let Then can we construct a stochastic matrix S, which maps the vector of probabilities induced by measuring |ψ , to the vector induced by measuring U |ψ ? Trivially yes. The following matrix maps any vector of probabilities to − → q , ignoring the input vector − → p entirely: Here PT stands for product theory. The product theory corresponds to a strange picture of physical reality, in which memories and records are completely unreliable, there being no causal connection between states of affairs at earlier and later times. So we would like S to depend on U itself somehow, not just on |ψ and U |ψ . Indeed, ideally S would be a function only of U , and not of |ψ . But this is impossible, as the following example shows. Let U be a π/4 rotation, and let |+ = (|0 + |1 ) / On the other hand, it is easy to see that, if S can depend on |ψ as well as U , then there are infinitely many choices for the function S (|ψ , U ). Every choice reproduces the predictions of quantum mechanics perfectly when restricted to single-time probabilities. So how can we possibly choose among them? Our approach in Sections 2 and 4 will be to write down axioms that we would like S to satisfy, and then investigate which of the axioms can be satisfied simultaneously.
Formally, a hidden-variable theory is a family of functions {S N } N ≥1 , where each S N maps an N -dimensional mixed state ρ and an N × N unitary matrix U onto a singly stochastic matrix S N (ρ, U ). We will often suppress the dependence on N , and use subscripts such as PT or FT to indicate the theory in question. Also, if ρ = |ψ ψ| is a pure state we may write S (|ψ , U ) instead of S (|ψ ψ| , U ).
Let (M ) ij denote the entry in the i th column and j th row of matrix M . Then (S) ij is the probability that the hidden variable takes value |j after U is applied, conditioned on it taking value |i before U is applied. At a minimum, any theory must satisfy the following marginalization axiom: for all j ∈ {1, . . . , N }, This says that after U is applied, the hidden variable takes value |j with probability U ρU −1 jj , which is the usual Born probability.
Often it will be convenient to refer, not to S itself, but to the matrix P (ρ, U ) of joint probabilities whose (i, j) entry is (P ) ij = (S) ij (ρ) ii . The i th column of P must sum to (ρ) ii , and the j th row must sum to U ρU −1 jj . Indeed, we will define the theories FT and ST by first specifying the matrix P , and then setting (S) ij := (P ) ij / (ρ) ii . This approach has the drawback that if (ρ) ii = 0, then the i th column of S is undefined. To get around this, we adopt the convention that where ρ ε = (1 − ε) ρ + εI and I is the N × N maximally mixed state. Technically, the limits lim ε→0 + (P (ρ ε , U )) ij (ρ ε ) ii might not exist, but in the cases of interest to us it will be obvious that they do.

Comparison with Previous Work
Before going further, we should contrast our approach with previous approaches to hidden variables, the most famous of which is Bohmian mechanics [5]. Our main criticism of Bohmian mechanics is that it commits itself to a Hilbert space of particle positions and momenta. Furthermore, it is crucial that the positions and momenta be continuous, in order for particles to evolve deterministically. To see this, let |L and |R be discrete positions, and suppose a particle is in state |L at time t 1 , and state (|L + |R ) / √ 2 at a later time t 2 . Then a hidden variable representing the position would have entropy 0 at t 1 , since it is always |L then; but entropy 1 at t 2 , since it is |L or |R both with 1/2 probability. Therefore the earlier value cannot determine the later one. 1 It follows that Bohmian mechanics is incompatible with the belief that all physical observables are discrete. But in our view, there are strong reasons to hold that belief, which include black hole entropy bounds; the existence of a natural minimum length scale (10 −33 cm); results on area quantization in quantum gravity [21]; the fact that many physical quantities once thought to be continuous have turned out to be discrete; the infinities of quantum field theory; the implausibility of analog "hypercomputers"; and conceptual problems raised by the independence of the continuum hypothesis.
Of course there exist stochastic analogues of Bohmian mechanics, among them Nelsonian mechanics [19] and Bohm and Hiley's "stochastic interpretation" [6]. But it is not obvious why we should prefer these to other stochastic hidden-variable theories. From a quantum-information perspective, it is much more natural to take an abstract approach-one that allows arbitrary finitedimensional Hilbert spaces, and that does not rule out any transition rule a priori.
Stochastic hidden variables have also been considered in the context of modal interpretations; see Dickson [8], Bacciagaluppi and Dickson [2], and Dieks [10] for example. However, the central assumptions in that work are extremely different from ours. In modal interpretations, a pure state evolving unitarily poses no problems at all: one simply rotates the hidden-variable basis along with the state, so that the state always represents a "possessed property" of the system in the current basis. Difficulties arise only for mixed states; and there, the goal is to track a whole set of possessed properties. By contrast, our approach is to fix an orthogonal basis, then track a single hidden variable that is an element of that basis. The issues raised by pure states and mixed states are essentially the same.
Finally we should mention the consistent-histories interpretation of Griffiths [16] and Gell-Mann and Hartle [14]. This interpretation assigns probabilities to various histories through a quantum system, so long as the "interference" between those histories is negligible. Loosely speaking, then, the situations where consistent histories make sense are precisely the ones where the question of transition probabilities can be avoided.

Objections
Hidden-variable theories, as we define them, are open to several technical objections. For example, we required transition probabilities for only one orthogonal observable. What about other observables? The problem is that, according to the Kochen-Specker theorem, we cannot assign consistent values to all observables at any single time, let alone give transition probabilities for those values. This is an issue in any setting, not just ours. The solution we prefer is to postulate a fixed orthogonal basis of "distinguishable experiences," and to interpret a measurement in any other basis as a unitary followed by a measurement in the fixed basis. As mentioned in Section 1.2, modal interpretations opt for a different solution, which involves sets of bases that change over time with the state itself. It might be interesting to combine the approaches.
Another objection is that the probability of transitioning from basis state |i at time t 1 to basis state |j at time t 2 might depend on how finely we divide the time interval between t 1 and t 2 . In other words, for some state |ψ and unitaries V, W , we might have (a similar point was made by Gillespie [15]). Indeed, this is true for any hidden-variable theory other than the product theory PT . To see this, observe that for all unitaries U and states |ψ , there exist unitaries V, W such that U = W V and V |ψ = |1 . Then applying V destroys all information in the hidden variable (that is, decreases its entropy to 0); so if we then apply W , then the variable's final value must be uncorrelated with the initial value. In other words, S (V |ψ , W ) S (|ψ , V ) must equal S PT (|ψ , U ). It follows that to any hidden-variable theory we must associate a time scale, or some other rule for deciding when the transitions take place.
In our defense, let us point out that exactly the same problem arises in continuous-time stochastic hidden-variable theories. For if a state |ψ is governed by the Schrödinger equation d |ψ /dt = iH t |ψ , and a hidden variable's probability distribution − → p is governed by the stochastic Finally, it will be objected that we have ignored special relativity. In Section 2 we will define a commutativity axiom, which informally requires that the stochastic matrix S not depend on the temporal order of spacelike separated events. Unfortunately, we will see that when entangled states are involved, commutativity is irreconcilable with another axiom that seems even more basic. The resulting nonlocality has the same character as the nonlocality of Bohmian mechanics-that is, one cannot use it to send superluminal signals in the usual sense, but it is unsettling nonetheless.

Axioms for Hidden-Variable Theories
We now state seven axioms that we would like hidden-variable theories to satisfy.
Symmetry. A theory is symmetric if it is invariant under relabeling of basis states: that is, if for all ρ, U and all permutation matrices Q, All theories discussed in this paper are symmetric.
Indifference. Suppose we partition the basis states into 'blocks,' between which U can never produce interference. Call an ordered pair I, J of subsets of {1, . . . , N } a block if (U ) ij = 0 for all i ∈ I and j / ∈ J, as well as all i / ∈ I and j ∈ J. Also, call I, J a minimal block if |I| = |J| and no I * , J * with I * ⊂ I and J * ⊂ J is a block. Note that if I 1 , J 1 , . . . , I m , J m are the minimal blocks, then both {I 1 , . . . , I m } and {J 1 , . . . , J m } are partitions of {1, . . . , N }. We say a theory is indifferent if it never produces interference between minimal blocks-that is, if (S) ij = 0 for all i, j in different minimal blocks. In particular, indifference implies that given any state ρ in a tensor product space H A ⊗ H B , and any unitary U that acts only on H A (that is, is the identity on H B ), the stochastic matrix S (ρ, U ) acts only on H A as well.
Robustness. A theory is robust if it is insensitive to small errors in a state or unitary (which, in particular, implies continuity). Suppose we obtain ρ and U by making small changes to ρ and U respectively. Then for all polynomials p, there should exist a polynomial q such that for all N , where M = max ij (M ) ij , whenever ρ − ρ ≤ 1/q (N ) and U − U ≤ 1/q (N ). Robustness has an important advantage for quantum computing: if a hidden-variable theory is robust then the set of gates used to define the unitaries U 1 , . . . , U T is irrelevant, since by the Solovay-Kitaev Theorem (see [20]), any universal quantum gate set can simulate any other to a precision ε with O (log c 1/ε) overhead.
Block Robustness. Unfortunately, one of the theories that we wish to study does not satisfy robustness. We therefore define a weaker notion of robustness that this theory satisfies. We say a hidden-variable theory is block robust if robustness holds for all modifications ρ, U → ρ, U such that U and U have the same set I 1 , J 1 , . . . , I m , J m of minimal blocks.
Commutativity. Let ρ AB be a bipartite state, and let U A and U B act only on subsystems A and B respectively. Then commutativity means that the order in which U A and U B are applied is irrelevant: of ρ into pure states. Theorem 2, part (ii) will show that the analogous axiom for P (ρ, U ) is unsatisfiable.

Comparing Hidden-Variable Theories
To fix ideas, let us compare some hidden-variable theories with respect to the above axioms. We have already seen the product theory PT in Section 1.1. It is easy to show that PT satisfies symmetry, robustness, commutativity, and decomposition invariance. However, we consider PT unsatisfactory because it violates indifference: even if a unitary U acts only on the first of two qubits, S PT (ρ, U ) will readily produce transitions between (say) |00 and |01 , or between |01 and |10 .
Recognizing this problem, Dieks [10] proposed an alternative theory that in our terminology corresponds to the following. 2 First find the minimal blocks I 1 , J 1 , . . . , I m , J m of U . Then apply the product theory separately to each minimal block; that is, if i and j belong to the same block I, J then set and otherwise set (S) ij = 0. The resulting Dieks theory, DT , clearly satisfies indifference. However, it does not satisfy robustness (or even continuity), since the set of minimal blocks can change if we replace '0' entries in U by arbitrarily small nonzero entries. In Section 4 we will introduce two other hidden-variable theories, the flow theory FT and the Schrödinger theory ST . The following table lists which axioms the four theories satisfy.

Impossibility Results
This section shows that certain sets of axioms cannot be satisfied by any hidden-variable theory. We first show that the failure of DT , FT , and ST to satisfy commutativity is inherent, and not a fixable technical problem.

Theorem 1 No hidden-variable theory satisfies both indifference and commutativity.
Proof. Assume indifference holds, and let our initial state be |ψ = (|00 + |11 ) / √ 2. Suppose U A applies a π/8 rotation to the first qubit, and U B applies a −π/8 rotation to the second qubit. Then Let v t be the value of the hidden variable after t unitaries have been applied. Let E be the event that v 0 = |00 initially, and v 2 = |10 at the end. If U A is applied before U B , then the unique 'path' from v 0 to v 2 consistent with indifference sets v 1 = |10 . So But if U B is applied before U A , then the probability that v 0 = |11 and v 2 = |10 is at most 1 2 sin 2 π 8 , by the same reasoning. Thus, since v 2 must equal |10 with probability 1/4, and since the only possibilities for v 0 are |00 and |11 , We conclude that commutativity is violated. Let us remark on the relationship between Theorem 1 and Bell's Theorem. Any hiddenvariable theory that is "local" in Bell's sense would immediately satisfy both indifference and commutativity. However, the converse is not obvious, since there might be nonlocal information in the states U A |ψ or U B |ψ , which an indifferent commutative theory could exploit but a local one could not. Theorem 1 rules out this possibility, and in that sense is a strengthening of Bell's Theorem.
The next result places limits on decomposition invariance.
(ii) No theory has the property that Proof.
Our last impossibility result says that no hidden-variable theory satisfies both indifference and "strong continuity," in the sense that for all ε > 0 there exists This is the reason why we defined robustness in terms of the joint probabilities matrix P rather than the stochastic matrix S. On the other hand, note that by giving up indifference, we can satisfy strong continuity, as is shown by FT .

Specific Theories
This section presents the main results of the paper, which concern two nontrivial examples of hidden-variable theories: the flow theory in Section 4.1, and the Schrödinger theory in Section 4.2.

Flow Theory
The idea of the flow theory is to convert a unitary matrix into a weighted directed graph, and then route probability mass through that graph like oil through pipes. Given a unitary U , let    are pure states. Then consider the network G shown in Figure 1. We have a source vertex s, a sink vertex t, and N input and N output vertices labeled by basis states |1 , . . . , |N . Each edge of the form (s, |i ) has capacity |α i | 2 , each edge (|i , |j ) has capacity (U ) ij , and each edge (|j , t) has capacity |β j | 2 . A natural question is how much probability mass can flow from s to t without violating the capacity constraints. Rather surprisingly, we show that one unit of mass (that is, all of it) can. Interestingly, this result would be false if edge (|i , |j ) had capacity (U ) ij 2 (or even (U ) ij 1+ε ) instead of (U ) ij . We also show that there exists a mapping from networks to maximum flows in those networks, that is robust in the sense that a small change in edge capacities produces only a small change in the amount of flow through any edge.
The proofs of these theorems use classical results from the theory of network flows (see [7] for an introduction). In particular, let a cut be a set of edges that separates s from t; the value of a cut is the sum of the capacities of its edges. Then a fundamental result called the Max-Flow-Min-Cut Theorem [11] says that the maximum possible amount of flow from s to t equals the minimum value of any cut.
Theorem 3 One unit of flow can be routed from s to t in G.
Proof. By the above, it suffices to show that any cut C in G has value at least 1. Let A be the set of i ∈ {1, . . . , N } such that (s, |i ) / ∈ C, and let B be the set of j such that (|j , t) / ∈ C. Then C must contain every edge (|i , |j ) such that i ∈ A and j ∈ B, and we can assume without loss of generality that C contains no other edges. So the value of C is Therefore we need to prove the matrix inequality Let U be fixed, and consider the maximum of the right-hand side over all |ψ . Since So letting θ be the angle between H A and H B , λ = 2 cos 2 θ 2 = 1 + cos θ which completes the theorem. Observe that Theorem 3 still holds if U acts on a mixed state ρ, since we can write ρ as a convex combination of pure states |ψ ψ|, construct a flow for each |ψ separately, and then take a convex combination of the flows.
Using Theorem 3, we now define the flow theory FT . Let F (ρ, U ) be the set of maximum flows for ρ, U -representable by N × N arrays of real numbers f ij such that 0 ≤ f ij ≤ (U ) ij for all i, j, and also Clearly F (ρ, U ) is a convex polytope, which Theorem 3 asserts is nonempty. Form a maximum flow f * (ρ, U ) ∈ F (ρ, U ) as follows: first let f * 11 be the maximum of f 11 over all f ∈ F (ρ, U ). Then let f * 12 be the maximum of f 12 over all f ∈ F (ρ, U ) such that f 11 = f * 11 . Continue to loop through all i, j pairs in lexicographic order, setting each f * ij to its maximum possible value consistent with the (i − 1) N + j − 1 previous values.
We define the joint probabilities matrix P by "symmetrizing" f * (ρ, U ) over permutations of basis states-that is, where Q ranges over all N × N permutation matrices. As discussed in Section 1.1, given P we can easily obtain the stochastic matrix S by dividing the i th column by (ρ) ii , or taking a limit in case (ρ) ii = 0. It is easy to check that FT so defined satisfies the symmetry and indifference axioms. Showing that FT satisfies robustness is harder. Our proof is based on the Ford-Fulkerson algorithm [11], a classic algorithm for computing maximum flows that works by finding a sequence of "augmenting paths," each of which increases the flow from s to t by some positive amount.

Theorem 4 FT satisfies robustness.
Proof. Let G be an arbitrary flow network with source s, sink t, and directed edges e 1 , . . . , e m , where each e i has capacity c i and leads from v i to w i . It will be convenient to introduce a fictitious edge e 0 from t to s with unlimited capacity; then maximizing the flow through G is equivalent to maximizing the flow through e 0 . Suppose we produce a new network G by increasing a single capacity c i * by some ε > 0. Let f * be the optimal flow for G, obtained by first maximizing the flow f 0 through e 0 , then maximizing the flow f 1 through e 1 holding f 0 fixed, and so on up to f m . Let f * be the maximal flow for G produced in the same way. We claim that for all i ∈ {0, . . . , m}, To see that the theorem follows from this claim: first, if f * is robust under adding ε to c i * , then it must also be robust under subtracting ε from c i * . Second, if we change ρ, U to ρ, U such that ρ − ρ ≤ 1/q (N ) and U − U ≤ 1/q (N ), then we can imagine the N 2 + 2N edge capacities are changed one by one, so that (Here we have made no attempt to optimize the bound.) Third, symmetrizing over all row and column permutations can only decrease P − P , not increase it.
We now prove to the claim. To do so we describe an iterative algorithm for computing f * . First maximize the flow f 0 through e 0 , by using the Ford-Fulkerson algorithm [11] to find a maximum flow from s to t. Let f (0) be the resulting flow, and let G (1) be the residual network that corresponds to f (0) . For each i, that is, G (1) has an edge e i = (v i , w i ) of capacity c i , and an edge i . Next maximize f 1 subject to f 0 by using the Ford-Fulkerson algorithm to find "augmenting cycles" from w 1 to v 1 and back to w 1 in G (1) \ {e 0 , e 0 }. Continue in this manner until each of f 1 , . . . , f m has been maximized subject to the previous f i 's. Finally set f * = f (m) . Now, one way to compute f * is to start with f * , then repeatedly "correct" it by applying the same iterative algorithm to maximize f 0 , then f 1 , and so on. Let ε i = f * i − f * i ; then we need to show that ε i ≤ ε for all i ∈ {0, . . . , m}. The proof is by induction on i. Clearly ε 0 ≤ ε, since increasing c i * by ε can increase the value of the minimum cut from s to t by at most ε. Likewise, after we maximize f 0 , the value of the minimum cut from w 1 to v 1 can increase by at most ε − ε 0 + ε 0 = ε. For of the at most ε new units of flow from w 1 to v 1 that increasing c i * made available, ε 0 of them were "taken up" in maximizing f 0 , but the process of maximizing f 0 could have again increased the minimum cut from w 1 to v 1 by up to ε 0 . Continuing in this way, and so on up to ε m . This completes the proof.

Schrödinger Theory
Our final hidden-variable theory, which we call the Schrödinger theory or ST , is the most interesting one mathematically. The idea-to make a matrix into a stochastic matrix via an iterative process of row and column rescaling-is natural enough that we came upon it independently, only later learning that it originated in a 1931 paper of Schrödinger [22]. Schrödinger gave a pair of functional integral equations that such an iterative process would solve, but was unable to prove that those equations always have a solution. The existence and uniqueness of a solution were shown under broad conditions by Nagasawa [18], building on earlier work of Fortet [12] and Beurling [4]. Our goal is to give what (to our knowledge) is the first self-contained, reasonably accessible presentation of the main result in this area; and to interpret that result in what we think is the correct way: as providing one example of a hidden-variable theory, whose strengths and weaknesses should be directly compared to those of other theories.
Most of the technical difficulties in [4,12,18,22] arise because the stochastic process being constructed involves continuous time and particle positions. Here we eliminate those difficulties by restricting attention to discrete time and to finite-dimensional Hilbert spaces. We thereby obtain a generalized version 3 of a problem that computer scientists know as (r, c)-scaling of matrices. Sinkhorn [23] gave an algorithm for the (r, c)-scaling problem, which was shown to run in polynomial time by Franklin and Lorenz [13] (see also Linial, Samorodnitsky, and Wigderson [17]).
As in the case of the flow theory, given a unitary U acting on a state ρ, the first step is to replace each entry of U by its absolute value, obtaining the nonnegative matrix U (0) defined by U (0) ij := (U ) ij . We then repeatedly tweak U (0) to bring it closer to a joint probabilities matrix P (ρ, U ). We want to make the i th column of the matrix sum to (ρ) ii , and the j th row sum to U ρU −1 jj for all i, j ∈ {1, . . . , N }. The stochastic matrix S (ρ, U ) is then readily obtained by normalizing each column to sum to 1.
The algorithm is iterative. For each t ≥ 0 we obtain U (2t+1) by normalizing each column i of U (2t) to sum to (ρ) ii ; likewise we obtain U (2t+2) by normalizing each row j of U (2t+1) to sum to U ρU −1 jj . More formally, The crucial fact is that the above iteration converges. Our proof will reuse a result about network flows from Section 4.1, in order to define a nondecreasing "progress measure" based on Kullback-Leibler distance.
Given any such array, define a progress measure where we adopt the convention 0 0 = 1. We claim that Z (t+1) ≥ Z (t) for all t ≥ 1. To see this, assume without loss of generality that we are on an odd step 2t + 1, and let C ij be the i th column sum before we normalize it. Then As a result of the 2t th normalization step, we had i C (2t) i = 1. Subject to that constraint, the maximum of ii for all i-a simple calculus fact that follows from the nonnegativity of Kullback-Leibler distance. This implies that Z (2t+1) ≥ Z (2t) . Similarly, normalizing rows leads to Z (2t+2) ≥ Z (2t+1) .
It follows that the limit U (∞) = lim t→∞ U (t) exists. For suppose not; then some C (t) i is bounded away from (ρ) ii , so there exists an ε > 0 such that Z (t+1) ≥ (1 + ε) Z (t) for all even t. But this is a contradiction, since Z (0) > 0 and Z (t) ≤ 1 for all t.
It is immediate that ST satisfies symmetry and indifference. Let us show that it satisfies product commutativity as well.
Proof. Given a state |ψ = |ψ A ⊗ |ψ B , let U A ⊗ I act only on |ψ A and let I ⊗ U B act only on |ψ B . Then we claim that S (|ψ , U A ⊗ I) = S (|ψ A , U A ) ⊗ I.
The reason is simply that multiplying all amplitudes in |ψ A and U A |ψ A by a constant factor α x , as we do for each basis state |x of |ψ B , has no effect on the scaling procedure that produces S (|ψ A , U A ). Similarly S (|ψ , I ⊗ U B ) = I ⊗ S (|ψ B , U B ) . On the other hand, let us show that ST violates decomposition invariance. Using the same notation as in Section 4.1, we have R π/8 IR −1 π/8 = I, R π/8 ϕ π/8 = ϕ π/4 , and R π/8 ϕ 5π/8 = ϕ 3π/4 , from which it can be calculated that

Discussion
The idea that certain observables in quantum mechanics might have trajectories governed by dynamical laws has reappeared many times: in Schrödinger's 1931 stochastic approach [22], Bohmian mechanics [5], modal interpretations [2,8,10], and elsewhere. Yet because all of these proposals yield the same predictions for single-time probabilities, if we are to decide between them it must be on the basis of internal mathematical considerations. A main message of this paper has been that such considerations can actually get us quite far. To focus attention on the core issues, we restricted attention to the simplest possible setting: discrete time, a finite-dimensional Hilbert space, and a single orthogonal basis. Within this setting, we proposed what seem like reasonable axioms that any hidden-variable theory should satisfy: for example, symmetry under permutation of basis states, robustness to small perturbations, and independence of the temporal order of spacelike-separated events. We then showed that not all of these axioms can be satisfied simultaneously. But perhaps more surprisingly, we also showed that certain subsets of axioms can be satisfied for highly nontrivial reasons. In showing that the indifference and robustness axioms can be simultaneously satisfied, Section 4 revealed an unexpected connection between unitary matrices and the classical theory of network flows.
As mentioned previously, the most important open problem is to show that the Schrödinger theory satisfies robustness. Currently, we can only show that the matrix P ST (ρ, U ) is robust to exponentially small perturbations, not polynomially small ones. The problem is that if any row or column sum in the U (t) matrix is extremely small, then the (r, c)-scaling process will magnify tiny errors in the entries. Intuitively, though, this effect should be washed out by later scaling steps.
A second open problem is whether there exists a theory that satisfies indifference, as well as commutativity for all separable mixed states (not just separable pure states). A third problem is to investigate other notions of robustness-for example, robustness to small multiplicative rather than additive errors.

Acknowledgments
I thank Umesh Vazirani, Ronald de Wolf, and an anonymous reviewer for comments on an earlier version of this paper; Dorit Aharonov, Guido Bacciagaluppi, John Preskill, and Avi Wigderson for helpful discussions; and Dennis Dieks for correspondence.