Bugs from the Future: Hadamard Coins and Implicit Measurement | Hacker News Reader

Bugs from the Future: Hadamard Coins and Implicit Measurement

algassert.com

63 pointsStrilanc9 comments

Ah, so quantum computation is even more subtly affected by evaluation semantics than non-strict languages. That was a very clear and enjoyable explanation!

Note to self: start working qrust now, before it becomes a big problem.

It's actually really difficult to determine if a given action will decohere the condition, which makes the language design issue interesting.

For example, consider this code:

    if (q1 != q2) != (H(q1) != H(q2)):
        apply Y to q1

Acting on a qubit used in the condition is a great way to ruin attempts to uncompute said condition. But actually, if you compile this into a circuit, the ancilla used to hold the condition uncomputes just fine:

https://goo.gl/VD5Z2t

It has to with the fact that we're measuring X and Z parities of these two qubits, and yes applying a Y gate affects those parities, but it flips both so the parity-of-parities stays the same.

(And this is on top of all the classical obstacles to perfect classification, like the halting problem.)

I'm probably grossly misunderstanding this, but there's no way that you could have a "force a measurement" operator and/or a "caught you peeking" predicate in a language for quantum computers?

Forcing a measurement is easy. The language would have something like:

    result = measure q

Forgetting to use that was the source of the bug in the post. The code should have read `if measure qubit`.

'Caught you peeking' depends on what you mean. Measurement has effects that matter, and you can check for those effects. You run the circuit many times, collect statistics, and thereby figure out what the black box is doing. But there's no primitive operation like "is qubit not measured".

By "caught you peeking" I meant something reminiscent of the "taint" mechanism you see in languages like Perl and Ruby. Once the qubit was measured, it would be marked so, and the compiler or interpreter would complain if you attempted to use it as if it were unmeasured.

Oh, yes, you can of course use a static or runtime type system to try to keep track of that kind of thing.

The tricky thing is that measurement isn't always associated with a single qubit. For example, consider:

    if q1 != q2:
        apply H to q1

This code will cause some decoherence, because we need q1's original value to uncompute the condition but we changed it. But that decoherence isn't specifically associated with just q1, it will also hit q2 because the thing we decohered was the parity between the two.

Now you could detect this happening at runtime, sometimes. The ancilla holding the condition value fails to uncompute consistently, so it will sometimes end up ON. The runtime could notice that ON ancilla and warn you that an ancilla failed to uncompute, but there could be many many actions in between that ancilla being computed and uncomputed. It's hard to figure out which action or combination of actions is the problem, and it's hard to figure out what exactly was decohered. Plus this check is only probabilistic; decoherence is a property of the program not the ancilla's final state. Decoherence still happened if the ancilla ended up OFF but could have ended up ON.

Static types are the qrusty way to do it. Runtime bookkeeping is wasteful.

Thanks. I'm going to take a while to process that. :-)

Reply on news.ycombinator.com