Gil Kalai’s blog

## Drunken Time and Drunken Computation

Posted on May 4, 2010 by

### The problem

We are used to computer programs or models for computations that perform at time $i$ step $U_i$, $i=1,2,\dots,N$.  Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time $i$ step $\pi(i)$, where $\pi$ 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 $n$ variables $x_1,x_2,\dots, x_n$. 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 $U_i$?

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) $U_i$ is a transformation where the value of each variable $x_i$ 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 $x(i) = i + Y$, where $Y$ is a normally distributed random variable with standard deviation $\epsilon n$, and define $\pi (i)$ based on the ordering of the $x(i)$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 $U_i$‘s are the same? Several participants in the seminar commented that we can have universal classical computation when we run the same step $U_i$ 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 $n >> N$ 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.

### Like this:

This entry was posted in Computer Science and Optimization. Bookmark the permalink.

### 10 Responses to Drunken Time and Drunken Computation

1. Martin Schwarz says:

You may want to check out the related paper http://arxiv.org/abs/0809.0847, where a model of quantum computation with commuting gates is analyzed, i.e. the order of gate applications is irrelevant. Yet the model seems to be rich enough to create probability distributions which are hard to sample from classically.

2. Jack says:

Do you have a reference for the Itamar Pitowski result?

3. alef says:

Consider n bits placed on a cycle of size n. A bit per vertex.
You don’t see the bits scenery. A walker preforming simple random walk on the cycle broadcast to you at each time step the bit placed where she is.

1. It is possible to reconstruct the scenery.
2. Polynomial many observations are sufficient with high probability.
3. We don’t know an efficient algorithm with polynomially many operations,
to recover the scenery from the polynomial many observations though

4. Gil Kalai says:

Thanks for the comments Martin and Alef,
Jack, I found the following link
http://edelstein.huji.ac.il/staff/pitowsky/papers/Paper14.pdf
for a 1990 paper by Pitowski entitled “The Physical Church’s Thesis and Physical Computational Complexity”.

5. jonas says:

So this would be like the 2001/westley entry in IOCC?

6. a says:

Isn’t distributed computing lower bounds kind of what you want for order of computation being specified by an adversary?

7. Gil Kalai says:

Oded Regev gave a simple argument how to simulate an arbitrary quantum circuit by a quantum process with drunken time. See updated post.

8. JimM says:

It sounds like the problem is solved now, but for C in the quantum case you could consider local Hamiltonians. That might be too artificial.

9. Gil Kalai says:

Right, It looks that for the quantum case even B and most likely A allow universal quantum computing. This is the case even when time is completely random. It is even possible that you can do it with applying the same unitary operator at each step, but I am not sure about it.

Another question is if universal quantum computing prevails (or perhaps we are left with BPP) when we have drunken time plus the most simple noise applying to the qubits. (We can assume that gates are noiseless.)

10. Hola says:

\sum_{i=0}^n {\mathcal{J}_i}

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 19, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9046868681907654, "perplexity_flag": "middle"}