> import Data.Map (toList,fromListWith) > import Complex > infixl 7 .* > data W b a = W { runW :: [(a,b)] } deriving (Eq,Show,Ord) > mapW f (W l) = W $ map (\(a,b) -> (a,f b)) l > instance Functor (W b) where > fmap f (W a) = W $ map (\(a,p) -> (f a,p)) a > instance Num b => Monad (W b) where > return x = W [(x,1)] > l >>= f = W $ concatMap (\(W d,p) -> map (\(x,q)->(x,p*q)) d) (runW $ fmap f l) > a .* b = mapW (a*) b > instance (Eq a,Show a,Num b) => Num (W b a) where > W a + W b = W $ (a ++ b) > a - b = a + (-1) .* b > _ * _ = error "Num is annoying" > abs _ = error "Num is annoying" > signum _ = error "Num is annoying" > fromInteger a = if a==0 then W [] else error "fromInteger can only take zero argument" > collect :: (Ord a,Num b) => W b a -> W b a > collect = W . filter ((/= 0) . snd) . toList . fromListWith (+) . runW > type P a = W Float a > type Q a = W (Complex Float) a

Now consider this probability distribution:

> dice = sum [1/36 .* return (i,j) | i <- [1..6], j <- [1..6]]This corresponds to the usual distribution you expect from rolling two dice. As we know, under normal circumstances, the outcome of one die is doesn't depend on the other - in other words they are independent. We can express this independence mathematically as follows. First make the distribution for one die:

> die = sum [1/6 .* return i | i <- [1..6]]Now we can write code to make two independent die rolls:

> two_rolls = do > a <- die > b <- die > return (a,b)We find that

`dice`=

`two_rolls`. We can make this more generic by defining a joint distribution as follows:

> tensor dist1 dist2 = do > a <- dist1 > b <- dist2 > return (a,b)So

`tensor die die`=

`dice`. (This operation is actually a tensor product.) So now we can give a definition: if we have a distribution on

`(a,b)`, then the first and second components are said to be

*independent*if the distribution can be written as

`tensor dist1 dist2`for some choice of

`dist1`and

`dist2`. But so far I've only been talking about the probability monad. What about the quantum monad

`Q`? In that case the notion is almost identical, except the language is inverted. In that case, a distribution on

`(a,b)`is said to be entangled if it

*can't*be written as

`tensor state1 state2`. Despite all of the mystification in the popular literature, that's all it means. So why is entanglement important? One of the key ideas is this. Suppose we have a process that acts only one one part of a combined system. In other words, consider something like this:

> apply_part f x = do > (a,b) <- x > b' <- f b > return (a,b')If the two subcomponents are independent (or unentangled) so that

`x`=

`tensor dist1 dist2`then

`apply_part f x`=

`tensor dist1 (dist2 >>= f)`. In other words, if we're dealing with a distribution like

`tensor dist1 dist2`, and we're interested in studying operations on the second component, then we can completely ignore the first component during the process.

> coin = 0.75 .* return True + 0.25 .* return False > f x = 0.125 .* return x + 0.875 .* return (not x) > ex1 = collect (tensor coin (coin >>= f)) > ex2 = collect (apply_part f (tensor coin coin))

`ex1`=

`ex2`. Now suppose we have a combined system consisting of two parts: some subsystem, and its environment, ie. something of type

`(Environment,Subsystem)`. Then as long as the environment and the subsystem are independent, we can study the subsystem as if the environment weren't there. But now suppose information can 'leak' out from the subsystem. For example consider a process like:

> a `xor` b = a/=b > process x = do > (e,s) <- x > let e' = e `xor` s > return (e',s)Because there is some flow from

`s`to

`e'`, there is no guarantee that

`process x`has independent subparts. As a result, we can no longer treat

`s`as an independent subsystem, and theorems that are true about an independent

`s`no longer hold. For example, define:

> rotate :: Float -> Bool -> Q Bool > rotate theta True = let theta' = theta :+ 0 > in cos (theta'/2) .* return True - sin (theta'/2) .* return False > rotate theta False = let theta' = theta :+ 0 > in cos (theta'/2) .* return False + sin (theta'/2) .* return TrueWe know that

`return True >>= rotate (pi/10) >>= rotate (-pi/10)`gives us back the state we started with. Similarly, with

> pure x = do > (a,b) <- x > b' <- rotate (pi/10) b > b'' <- rotate (-pi/10) b' > return (a,b'')

`pure`acts as the identity on the second component. In particular,

`pure (e,True)`is the same as

`tensor e (return True)`because the terms involving

`false`cancel out. But if we have a 'leak' as in:

> impure x = do > (a,b) <- x > b' <- rotate (pi/10) b > a' <- return (a `xor` b') -- information flowing out > b'' <- rotate (-pi/10) b' > return (a',b'')and consider

`impure (e,True)`we end up with something where the

`False`terms don't cancel out. Compare

`collect $ pure $ return (False,False)`with

`collect $ impure $ return (False,False)`. We're familiar with the idea that something flowing into a system might mess it up. But here we have the situation that information flowing

*out*of a physical system can also mess it up. Any kind of entanglement between a system and its environment is called

*decoherence*. And what I've shown is that interactions between a system and its environment can cause a physical system to 'decohere', even if the direction of interaction appears to be only outwards.

And that's one reason why quantum computing is so hard. Not only must nothing in the environment affect our qubits, neither must any information about our qubits leave the system before we're ready to have them do so.

Anyway, now I'm equipped to start writing code to simulate quantum error correction...

Update: Tried to reuse some of this code and found a bug which I've now fixed. Sorry if this pops it to the front of various feeds. It's an old post.

Great post! Now I just need to load all this code in to an interpreter and mess around until I really understand it.

ReplyDeleteOnce again, many thanks for the cool articles.

That's a brilliant solution to the foolishness that is Num being a ring with valuation -- just apply the forgetful functor!

ReplyDeleteWhy didn't I think of that?

small typo:

ReplyDelete> e' <- e `xor` s

should be

> e' <- return $ e `xor` s