Mike's interests

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:

https://www.khanacademy.org/computer-programming/wireworld/6042139425570816

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:

https://kylehovey.github.io/CALSim/index.html .

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:

https://www.khanacademy.org/computer-programming/wireworld/6042139425570816

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:

https://kylehovey.github.io/CALSim/index.html .

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 https://arxiv.org/abs/quant-ph/0004091). 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 (https://arxiv.org/abs/quant-ph/9612026) 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.

https://arxiv.org/abs/quant-ph/0610130

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.

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

Post has attachment

Wait while more posts are being loaded