Profile cover photo
Profile photo
Mike Stay
Mike's interests
View all
Mike's posts

Post has attachment
While living in Guatemala in the early 90s, I had no access to computers for a couple of years. To keep myself from going mad, I tried to remember how the "wireworld" cellular automaton worked. I misremembered it, but the way I misremembered it made certain components like crossovers much easier at the cost of some components being slightly larger; for example, a diode needs two empty cells in the middle instead of just one. The tiny crossovers mean that under my rules, a full adder fits in a mere 13x7 rectangle. The image below shows the adder and two clocks that try out all four inputs over sixteen cycles. In Guatemala I built a small CPU with some RAM on graph paper.

In both CAs, there are four states called EMPTY, TAIL, HEAD, and WIRE. HEAD-TAIL pairs are excitations of a wire usually referred to as "electrons". EMPTY always remains EMPTY, HEAD becomes TAIL, and TAIL becomes WIRE. The difference is in how WIRE becomes HEAD. In the original CA, any WIRE cell bordering one or two HEAD cells becomes a HEAD. Under my rules, the same is roughly true, but electrons can turn by at most 45 degrees, so the neighborhood has a radius of 2 to allow checking where the tail of the electron is relative to the head.

Here's an implementation of the CA using my rules:
Right-clicking draws EMPTY. Clicking draws whatever the current cell type is: press space to draw WIRE, 'h' to draw HEADs, and 't' to draw TAILs. Press 'c' to remove all the electrons. Press 's' to step forward in the simulation.

You can play the original here: .


Post has attachment
Time-independent Hamiltonians for Grover's algorithm and NP-completeness

Here's an argument against the possibility of implementing Grover's algorithm as a time-independent Hamiltonian.

Let n be the number of qubits and N=2ⁿ. A time-independent Hamiltonian that implements Grover's algorithm will be of the form
 H = I + ε (|end><start|-|start><end|)
(see The eigenvectors of H with nonzero eigenvalues are very nearly

 |±> = 1/sqrt(2)(|end> ± i|start>);

the corresponding eigenvalues are very nearly ±π. The initial state is

 |start> = - i/sqrt(2) (|+> - |->),

a uniform superposition of the two eigenvectors that cancels out the marked state. Over a time T=O(sqrt(N)), it evolves to the marked state.

However, a measurement of the energy of the initial state under the time-independent Hamiltonian for Grover's algorithm will collapse it to one of |+> and |->. Measuring the energy of a state under this Hamiltonian takes constant time independent of N, because they differ from ±π by an exponentially small amount. This isn't true of Farhi and Gutmann's "analog analogue" of Grover's algorithm ( because the energies of the two states differ from each other by an exponentially small amount; measuring the energy difference under their Hamiltonian takes an exponentially long time.

When measuring either |+> or |-> in the qubit basis, we get the marked state with probability 1/2.

One way I can see that the argument above could fail is due to a branch cut: a unitary operation is generated by lots of Hamiltonians whose eigenvalues differ by 2π. If the eigenvalues are not ±(π - ε) but rather π ± ε, then the energy gap is exponentially small, just like Farhi and Gutmann's Hamiltonian.

These guys claim to have designed a time-independent implementation of Grover's algorithm, but I haven't worked out what the eigenvalues of their Hamiltonian are.
 Grover's algorithm on a Feynman computer
 Diego de Falco, Dario Tamascelli

 We present an implementation of Grover's algorithm in the framework of
 Feynman's cursor model of a quantum computer. The cursor degrees of
 freedom act as a quantum clocking mechanism, and allow Grover's
 algorithm to be performed using a single, time-independent
 Hamiltonian. We examine issues of locality and resource usage in
 implementing such a Hamiltonian. In the familiar language of
 Heisenberg spin-spin coupling, the clocking mechanism appears as an
 excitation of a basically linear chain of spins, with occasional
 controlled jumps that allow for motion on a planar graph: in this
 sense our model implements the idea of "timing" a quantum algorithm
 using a continuous-time random walk. In this context we examine some
 consequences of the entanglement between the states of the
 input/output register and the states of the quantum clock.

Post has attachment
Name-free combinators for concurrency

Lucius Gregory Meredith, Michael Stay

Yoshida demonstrated how to eliminate the bound names coming from the input prefix in the asynchronous pi calculus, but her combinators still depend on the "new" operator to bind names. We modify Yoshida's combinators by replacing "new" and replication with reflective operators to provide the first combinator calculus with no bound names into which the asynchronous pi calculus has a faithful embedding. We also show that multisorted Lawvere theories enriched over graphs suffice to capture the operational semantics of the calculus.

Post has attachment
Have type 1 diabetes or know someone who does? There are still 25 slots open in the phase 2 trial to test a potential cure. BCG has been used for decades as an immune booster for fighting TB, typically given to people when traveling to areas where they expect to be exposed to TB. It's already passed a phase 1 clinical trial to show there are no adverse effects.

Post has attachment

Post has attachment

Post has attachment

Post has attachment
Youtube on Chrome on OS X Yosemite is really screwed up. Any idea how to fix? Works fine on other browsers.

קבלה, חידה, והנחש, חטא...

Post has attachment
Shepard tone crochet hooks
Wait while more posts are being loaded