Drunken Time and Drunken Computation

The problem

We are used to computer programs or models for computations that perform at time  step , .  Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time  step , where is a random permutation which is substantially correlated with the identity permutation.  What then is our computational power?

I suggested this problem in our  rump session meeting of last  thursday quantum computation seminar. We have these sessions once every several months and usually they are very interesting.

What are the variables?

The computation is applied to variables . There are three variations to consider regarding the identity of these variables:

a) bits

b) qubits

c) algebraic variables

What do we allow for a single step ?

Here also we have three possibilities.

A) a single gate operating on a small number of variables.

B) applying as many gates as we want on disjoint sets of variables.

C)  is a transformation where the value of each variable is a function of a bounded set of variables (overlaps are ok). 

By a “gate” we refer to the standard notion of gates: Boolean gates for bits for case a), unitary transformation on a small number of qubits for case b) and algebraic gates for case c). (I dont know of an appropriate way to define option C for the quantum case.) 

What is the precise stochastic model?

Write , where  is a normally distributed random variable with standard deviation , and define based on the ordering of the s.

What happens if we consider fully random time evolution, or even adversarial time evolution?

We can ask for the computation power if we talk about completely random permutations. We can also let an adversary choose the permutation.  We can also ask, how well can we do if we want to compute something when all the ‘s are the same? Several participants in the seminar commented that we can have universal classical computation when we run the same step every times. (But this applies for variant C ). One argument raised by Elad Eban was based on known fact regarding cellular automata, and another argument raised by Or Sattath was based on a standard way to move from Turing machines to Boolean circuits. I do not know if we can replace variant C by variant B in these arguments, or,  if they apply to the quantum case.

What do I expect:

a) The classical case: I expect that classic computation prevails (for A and B as well). A rather vague suggestion is to take and simulate a classical computation by replacing every logical bit with a block of large number of physical bits, performing  the computation on pairs of such blocks, and apply “majority” repeatedly within the blocks to guarantee that the physical bits indeed represent the logical bits.

b) The quantum case: I don’t know. This may serve as a (rather wild) model where we cannot go beyond classical computation. (Well, not quite see the update.)

_____

Update

Oded Regev showed me a very simple argument how drunken time allows the full power of quantum computation. (Perhaps, the arguments by Elad, and Or can be extended to the quamtum case, and maybe the paper quoted in the remarks show it as well, but Oded’s argument is quite clear) Here it is:

 “Let’s have a clock register storing the clock in unary encoding. The unitary transformation corresponding to a gate at time t is the following:
* If the clock is at time t, advance it to t+1 and apply the gate
* If the clock is at time t+1, decrease it to t and apply the reverse of the gate
* Otherwise do nothing

Notice that you only need to consider three bits of the clock register (in addition to the two bits of the gate) to do this.

Now duplicate each unitary a sufficiently large number of times. I think what happens is that you get some kind of random walk on the clock register. Most steps do nothing, but with probability 1/T you advance forward, and with probability 1/T you go backwards. Therefore after about T*T^2=T^3 steps you expect the walk to reach time T, at which point you can simply read off the answer. By padding the circuit with identity gates you can increase the probability of measuring the final state of the circuit as much as you wish (so you need not worry about the final state being mixed).”

Further thoughts: Just a constant overhead?

An interesting question is: Is there a linear time algorithm to simulate a  an algorithm with T steps on a drunken time machine. This can be relevant for continuous time analogs where we can expect the drunken time effect at all time scales and a superlinear algorithm may blow up.

______

c) Algebraic variables. I don’t know.

Continuous-time analog?

We described a discrete-time model and it would be interesting to consider continuous time analogs of such drunken time evolution.

I do not know if stochastic perturbations based on “stochastic time-flow” of deterministic evolutions (e.g., those described  by differential equations) are equivalent to standard stochastic perturbations. 

Is time really drunk?

Various  “crazy” models regarding time were considered by physicists, mathematicians, and philosophers, and computer scientists for their own sake and also in connection to various models of computations.  Itamar Pitowsky showed how undecidable problems can be solved in finite time in certain hypothetical time/space structures. Dave Bacon studied quantum computation with quantum data that can traverse closed time-like curves and Aaronson and Watrous showed that closed time-like curves make quantum and classical computing equivalent (both allowing PSPACE computation). An example I learned from Moshe Vardi is modeling time as a tree that was proposed by Kripke following the introduction of temporal logic by Prior, and these ideas are playing a crucial role in the highly industrial area of automated verification.  (Remarks with more examples are most welcome.) (Of course, closed time  appeared earlier

I would expect that  models with “stochastic time flow”  have been considered in the physics and mathematics literature, so I’d be happy to have some pointers. Because of the Law of Large Numbers, small-scale stochastic processes look completely deterministic in larger scales. So if time is drunk in some scales we may not notice it in larger scales. (However, if time is really drunk, I would not expect the amount of drunkeness to be constant but rather to express some measure of non-classical behavior of the dynamics.)  Thinking of time as drunk may be lead (or perhaps has already led) to a mathematically useful device.