Mike Stay
Apr19-04, 02:19 AM
<jabberwocky><div class="vbmenu_control"><a href="jabberwocky:;" onClick="newWindow=window.open('','usenetCode','toolbar=no, location=no,scrollbars=yes,resizable=yes,status=no ,width=650,height=400'); newWindow.document.write('<HTML><HEAD><TITLE>Usenet ASCII</TITLE></HEAD><BODY topmargin=0 leftmargin=0 BGCOLOR=#F1F1F1><table border=0 width=625><td bgcolor=midnightblue><font color=#F1F1F1>This Usenet message\'s original ASCII form: </font></td></tr><tr><td width=449><br><br><font face=courier><UL><PRE>Deutch\'s algorithm with a pair of sunglasses and some mirrors\n\nMike Stay, 2004\n\n1. Introduction\n\nThe simplest quantum system is the quantum bit, or qubit. It\'s also\nabout the only quantum system that scales well enough that you can\nplay with it in your living room; in fact, it\'s likely that you have\nthe necessary materials strapped to your wrist right now. I\'m\ntalking about polarised light, and every digital watch, calculator,\nor other LCD device has a polarising film coating it. If you want\nto gain an intuition for the way quantum systems work, there is\nnothing better than playing with polarised light. You can order\nlarge polarised sheets from most science catalogs like Edmund\'s\nScientific, or you can go buy a pair of polarised sunglasses or some\ncheap digital watches and cannibalize them.\n\nPolarisers are to light like a picket fence is to a wave on a rope.\nYou can make a wave on a rope take nearly any shape you want: the\nwave could wiggle sideways, or up and down, or diagonally, or even be\nshaped like a corkscrew as it travels down the rope. The direction\nthe wave wiggles with respect to the rope is called its polarisation.\nIf you string the rope through a picket fence, only the part of the\nwave that wiggles in the same direction as the slot gets through to\nthe other side. The rest of the wave is absorbed by the fence and\nchanged to heat.\n\nThe thing that makes quantum computers more powerful than classical\nones is the effect we just saw in this example. Instead of having\nzero and one be opposites, like positive and negative, they are\northogonal. They are at right angles to each other, like up-down\nversus left-right; the difference between absorbed and transmitted\nis 90 degrees. It lets us take diagonal to mean "both zero and one\nat the same time" and do computations in parallel.\n\n2. Some trivial maths\n\nThe very first quantum algorithm that showed quantum computers were\nmore powerful than any classical computer is called Deutch\'s\nalgorithm; it only uses one qubit, and one can implement it with two\npolarisers and some mirrors. I\'ll explain how below, but first let\nme give some more background.\n\nThe only maths we need to describe everything in quantum computing\nis complex numbers and linear algebra--matrices and vectors with\ncomplex elements. In fact, for two of the most important quantum\nalgorithms, Deutch\'s algorithm and Grover\'s algorithm, we don\'t even\nneed complex numbers. This amounts to ignoring right- and left-\nhanded polarisations of light (the corkscrew-shaped waves).\n\nWhen we ignore these possibilities, we get what\'s called a "rebit".\nFormally, it\'s a pair of opposite points on the unit circle, a\ndouble-headed arrow at an angle w. The angle w is from 0 up to\n(but not including) 180 degrees. Physically, a rebit can be\nrepresented by polarised light of the kind mentioned above. The\nangle is measured from the absorbing axis of the polariser in front\nof our eyes. The point on the circle has two coordinates (a,t)\n[think "absorbed, transmitted"] given by\n\na = cos w and t = sin w.\n\nThe amount of light that\'s absorbed is a^2; the amount that\'s\ntransmitted is t^2. ("x^y" means "x to the power of y".) Since\n\ncos^2 w + sin^2 w = 100%,\n\nall the light is accounted for.\n\nFor example, if we had light polarised at 120 degrees, we\'d see that\n\nt^2 = sin^2 120 = (sqrt(3)/2)2 = 3/4 = 75%\n\nof the light is transmitted, while\n\na^2 = cos^2 120 = (-1/2)2 = 1/4 = 25%\n\nis absorbed.\n\n3. Deutch\'s algorithm\n\nDeutch\'s problem was the following. Given one of the functions\nf(x) from the sets {0,1} ("constant" functions) or {x,NOT x}\n("balanced" functions), figure out from which set it came by\ncomputing the value on one input. One bit of information is enough\nto distinguish the two sets, but classically there\'s no way of\ncalculating the bit we need, since it\'s the XOR of two function\noutputs. With a quantum computer, we get qubits for input and\noutput, and we can do better.\n\nJust as there are states "between" zero and one on a quantum\ncomputer, there are quantum gates that don\'t have classical\ncounterparts. One of these changes the sign of a or t. In\nclassical computing, the opposite of zero is one. In\nquantum computing, the opposite of up is down, but that\'s\nstill perpendicular to left-right! In practice, it\'s a\nreflection in a mirror.\n\nTwo reflections in a row are the same as a rotation, so we can\nreplace reflections horizontally and vertically with an optional\nrotation followed by an optional reflection. Rotation of\npolarisation is done with cellophane. Depending on what kind you\nget, you may see some pretty colors when you look at it between\npolarisers. This is the polarisation equivalent of a prism--just\nas a prism spreads out colors in space, some kinds of cellophane\nspread out colors in polarisation. So the first polariser fixes\nthe polarisation of the light, then the cellophane rotates each\ncolor differently, and the second polariser picks out a single\npolarisation and therefore a single color.\n\nSellotape brand adhesive tape gives (as far as I can tell) a perfect\n90 degree twist for optical frequencies. Two layers of it give\na 180 degree twist. (Now, since all the rebit arrows are double-\nended, a 180 degree rotation won\'t make any difference no matter\nwhich way the rebit is pointing. We can leave it out, and it won\'t\nmake any difference.)\n\nSo in the quantum version, we have four boxes that do the following:\n\n0: No rotation, even number of reflections\n1: 180 degree rotation, even number of reflections\nx: No rotation, odd number of reflections\nNOT x: 180 degree rotation, odd number of reflections\n\nIf you\'re familiar with matrix notation, these are\n\n0 => | 1 0| 1 => |-1 0| x => | 1 0| NOT x => |-1 0|\n| 0 1| | 0 -1| | 0 -1| | 0 1|\n\nor, most concisely\n\nf => |-1^f(0) 0|\n| 0 -1^f(1)|\n\nIf we choose a horizontal or vertical double-ended arrow, we won\'t\nbe able to tell if it was reflected: they\'re both symmetric\nhorizontally and vertically. These rebits correspond to the\nclassical inputs zero and one, and as before, we gain no\ninformation about which function it is. However, if we choose a\ndiagonal arrow, then Bob\'s our uncle.\n\nDeutch\'s algorithm, then, goes like this:\n\n1. Start with light polarised in the absorbing direction.\n2. Turn the black box so the light goes in diagonally.\n3. Shine the light that comes out of the black box through our\npolariser into our eyes. If we don\'t see any light, it\'s a\nconstant function; otherwise it\'s a balanced function.\n\n4. How to make it\n\nYou can build a black box by making a device that lets you choose\nan even or odd number of reflections while keeping the input and\noutput angles the same. It takes three mirrors and some cardboard.\n\nThe box should look like this:\n\n+---------------------+\n| /\n| /\n| /\n| |\n| |\n| |\n| |\n| |\n| |\n| / /|\n| / / |\n|/ / |\n+ ------------------+\n\nThe mirrors in the input and output corners should swivel between 45\ndegrees and 67.5 degrees. That gives two possibilities: at 45\ndegrees, we get light entering one port, bouncing to the mirror in\nthe near corner, then to the mirror in the far corner, and then out.\nSo at 45 degrees, the light bounces an odd number of times--a\nbalanced function. At 67.5 degrees, the light takes a path shaped\nlike three sides of a stop sign: it enters, bounces directly to the\nfar mirror, and bounces out. In this configuration, the light\nbounces twice--a constant function.\n\nIf you want to use the phase rotation, make a little frame for the two\nlayers of sellotape that will fit over one of the ports.\n\nThen with a torch and polarisers on the ports, you\'ll have yourself a\ntabletop quantum computer!\n\n--\nMike Stay\nhttp://www.cs.auckland.ac.nz/~msta039\n\n</UL></PRE></font></td></tr></table></BODY><HTML>');"> <IMG SRC=/images/buttons/ip.gif BORDER=0 ALIGN=CENTER ALT="View this Usenet post in original ASCII form"> View this Usenet post in original ASCII form </a></div><P></jabberwocky>Deutch's algorithm with a pair of sunglasses and some mirrors
Mike Stay, 2004
1. Introduction
The simplest quantum system is the quantum bit, or qubit. It's also
about the only quantum system that scales well enough that you can
play with it in your living room; in fact, it's likely that you have
the necessary materials strapped to your wrist right now. I'm
talking about polarised light, and every digital watch, calculator,
or other LCD device has a polarising film coating it. If you want
to gain an intuition for the way quantum systems work, there is
nothing better than playing with polarised light. You can order
large polarised sheets from most science catalogs like Edmund's
Scientific, or you can go buy a pair of polarised sunglasses or some
cheap digital watches and cannibalize them.
Polarisers are to light like a picket fence is to a wave on a rope.
You can make a wave on a rope take nearly any shape you want: the
wave could wiggle sideways, or up and down, or diagonally, or even be
shaped like a corkscrew as it travels down the rope. The direction
the wave wiggles with respect to the rope is called its polarisation.
If you string the rope through a picket fence, only the part of the
wave that wiggles in the same direction as the slot gets through to
the other side. The rest of the wave is absorbed by the fence and
changed to heat.
The thing that makes quantum computers more powerful than classical
ones is the effect we just saw in this example. Instead of having
zero and one be opposites, like positive and negative, they are
orthogonal. They are at right angles to each other, like up-down
versus left-right; the difference between absorbed and transmitted
is 90 degrees. It lets us take diagonal to mean "both zero and one
at the same time" and do computations in parallel.
2. Some trivial maths
The very first quantum algorithm that showed quantum computers were
more powerful than any classical computer is called Deutch's
algorithm; it only uses one qubit, and one can implement it with two
polarisers and some mirrors. I'll explain how below, but first let
me give some more background.
The only maths we need to describe everything in quantum computing
is complex numbers and linear algebra--matrices and vectors with
complex elements. In fact, for two of the most important quantum
algorithms, Deutch's algorithm and Grover's algorithm, we don't even
need complex numbers. This amounts to ignoring right- and left-
handed polarisations of light (the corkscrew-shaped waves).
When we ignore these possibilities, we get what's called a "rebit".
Formally, it's a pair of opposite points on the unit circle, a
double-headed arrow at an angle w. The angle w is from up to
(but not including) 180 degrees. Physically, a rebit can be
represented by polarised light of the kind mentioned above. The
angle is measured from the absorbing axis of the polariser in front
of our eyes. The point on the circle has two coordinates (a,t)
[think "absorbed, transmitted"] given by
a = cos w[/itex] and t = sin w.
The amount of light that's absorbed is a^2; the amount that's
transmitted is t^2. ("x^y" means "x to the power of y".) Since
cos^2 w + sin^2 w = 100%,
all the light is accounted for.
For example, if we had light polarised at 120 degrees, we'd see that
t^2 = sin^2 120 = (\sqrt(3)/2)2 = 3/4 = 75%
of the light is transmitted, while
a^2 = cos^2 120 = (-1/2)2 = 1/4 = 25%
is absorbed.
3. Deutch's algorithm
Deutch's problem was the following. Given one of the functions
f(x) from the sets {0,1} ("constant" functions) or {x,NOT x}
("balanced" functions), figure out from which set it came by
computing the value on one input. One bit of information is enough
to distinguish the two sets, but classically there's no way of
calculating the bit we need, since it's the XOR of two function
outputs. With a quantum computer, we get qubits for input and
output, and we can do better.
Just as there are states "between" zero and one on a quantum
computer, there are quantum gates that don't have classical
counterparts. One of these changes the sign of a or t. In
classical computing, the opposite of zero is one. In
quantum computing, the opposite of up is down, but that's
still perpendicular to left-right! In practice, it's a
reflection in a mirror.
Two reflections in a row are the same as a rotation, so we can
replace reflections horizontally and vertically with an optional
rotation followed by an optional reflection. Rotation of
polarisation is done with cellophane. Depending on what kind you
get, you may see some pretty colors when you look at it between
polarisers. This is the polarisation equivalent of a prism--just
as a prism spreads out colors in space, some kinds of cellophane
spread out colors in polarisation. So the first polariser fixes
the polarisation of the light, then the cellophane rotates each
color differently, and the second polariser picks out a single
polarisation and therefore a single color.
Sellotape brand adhesive tape gives (as far as I can tell) a perfect
90 degree twist for optical frequencies. Two layers of it give
a 180 degree twist. (Now, since all the rebit arrows are double-
ended, a 180 degree rotation won't make any difference no matter
which way the rebit is pointing. We can leave it out, and it won't
make any difference.)
So in the quantum version, we have four boxes that do the following:
0: No rotation, even number of reflections
1: 180 degree rotation, even number of reflections
x: No rotation, odd number of reflections
NOT x: 180 degree rotation, odd number of reflections
If you're familiar with matrix notation, these are
=> | 1 0| 1 => |-1 0| x => | 1 0| NOT x => |-1 0|| 1| |-1| |-1| | 1|
or, most concisely
f => |-1^f(0) 0|
| [itex]-1^f(1)|
If we choose a horizontal or vertical double-ended arrow, we won't
be able to tell if it was reflected: they're both symmetric
horizontally and vertically. These rebits correspond to the
classical inputs zero and one, and as before, we gain no
information about which function it is. However, if we choose a
diagonal arrow, then Bob's our uncle.
Deutch's algorithm, then, goes like this:
1. Start with light polarised in the absorbing direction.
2. Turn the black box so the light goes in diagonally.
3. Shine the light that comes out of the black box through our
polariser into our eyes. If we don't see any light, it's a
constant function; otherwise it's a balanced function.
4. How to make it
You can build a black box by making a device that lets you choose
an even or odd number of reflections while keeping the input and
output angles the same. It takes three mirrors and some cardboard.
The box should look like this:
+---------------------+
| /| /| /| || || || || || || / /|| / / ||/ / |
+ ------------------+
The mirrors in the input and output corners should swivel between 45
degrees and 67.5 degrees. That gives two possibilities: at 45
degrees, we get light entering one port, bouncing to the mirror in
the near corner, then to the mirror in the far corner, and then out.
So at 45 degrees, the light bounces an odd number of times--a
balanced function. At 67.5 degrees, the light takes a path shaped
like three sides of a stop sign: it enters, bounces directly to the
far mirror, and bounces out. In this configuration, the light
bounces twice--a constant function.
If you want to use the phase rotation, make a little frame for the two
layers of sellotape that will fit over one of the ports.
Then with a torch and polarisers on the ports, you'll have yourself a
tabletop quantum computer!
--
Mike Stay
http://www.cs.auckland.ac.nz/~msta039
Mike Stay, 2004
1. Introduction
The simplest quantum system is the quantum bit, or qubit. It's also
about the only quantum system that scales well enough that you can
play with it in your living room; in fact, it's likely that you have
the necessary materials strapped to your wrist right now. I'm
talking about polarised light, and every digital watch, calculator,
or other LCD device has a polarising film coating it. If you want
to gain an intuition for the way quantum systems work, there is
nothing better than playing with polarised light. You can order
large polarised sheets from most science catalogs like Edmund's
Scientific, or you can go buy a pair of polarised sunglasses or some
cheap digital watches and cannibalize them.
Polarisers are to light like a picket fence is to a wave on a rope.
You can make a wave on a rope take nearly any shape you want: the
wave could wiggle sideways, or up and down, or diagonally, or even be
shaped like a corkscrew as it travels down the rope. The direction
the wave wiggles with respect to the rope is called its polarisation.
If you string the rope through a picket fence, only the part of the
wave that wiggles in the same direction as the slot gets through to
the other side. The rest of the wave is absorbed by the fence and
changed to heat.
The thing that makes quantum computers more powerful than classical
ones is the effect we just saw in this example. Instead of having
zero and one be opposites, like positive and negative, they are
orthogonal. They are at right angles to each other, like up-down
versus left-right; the difference between absorbed and transmitted
is 90 degrees. It lets us take diagonal to mean "both zero and one
at the same time" and do computations in parallel.
2. Some trivial maths
The very first quantum algorithm that showed quantum computers were
more powerful than any classical computer is called Deutch's
algorithm; it only uses one qubit, and one can implement it with two
polarisers and some mirrors. I'll explain how below, but first let
me give some more background.
The only maths we need to describe everything in quantum computing
is complex numbers and linear algebra--matrices and vectors with
complex elements. In fact, for two of the most important quantum
algorithms, Deutch's algorithm and Grover's algorithm, we don't even
need complex numbers. This amounts to ignoring right- and left-
handed polarisations of light (the corkscrew-shaped waves).
When we ignore these possibilities, we get what's called a "rebit".
Formally, it's a pair of opposite points on the unit circle, a
double-headed arrow at an angle w. The angle w is from up to
(but not including) 180 degrees. Physically, a rebit can be
represented by polarised light of the kind mentioned above. The
angle is measured from the absorbing axis of the polariser in front
of our eyes. The point on the circle has two coordinates (a,t)
[think "absorbed, transmitted"] given by
a = cos w[/itex] and t = sin w.
The amount of light that's absorbed is a^2; the amount that's
transmitted is t^2. ("x^y" means "x to the power of y".) Since
cos^2 w + sin^2 w = 100%,
all the light is accounted for.
For example, if we had light polarised at 120 degrees, we'd see that
t^2 = sin^2 120 = (\sqrt(3)/2)2 = 3/4 = 75%
of the light is transmitted, while
a^2 = cos^2 120 = (-1/2)2 = 1/4 = 25%
is absorbed.
3. Deutch's algorithm
Deutch's problem was the following. Given one of the functions
f(x) from the sets {0,1} ("constant" functions) or {x,NOT x}
("balanced" functions), figure out from which set it came by
computing the value on one input. One bit of information is enough
to distinguish the two sets, but classically there's no way of
calculating the bit we need, since it's the XOR of two function
outputs. With a quantum computer, we get qubits for input and
output, and we can do better.
Just as there are states "between" zero and one on a quantum
computer, there are quantum gates that don't have classical
counterparts. One of these changes the sign of a or t. In
classical computing, the opposite of zero is one. In
quantum computing, the opposite of up is down, but that's
still perpendicular to left-right! In practice, it's a
reflection in a mirror.
Two reflections in a row are the same as a rotation, so we can
replace reflections horizontally and vertically with an optional
rotation followed by an optional reflection. Rotation of
polarisation is done with cellophane. Depending on what kind you
get, you may see some pretty colors when you look at it between
polarisers. This is the polarisation equivalent of a prism--just
as a prism spreads out colors in space, some kinds of cellophane
spread out colors in polarisation. So the first polariser fixes
the polarisation of the light, then the cellophane rotates each
color differently, and the second polariser picks out a single
polarisation and therefore a single color.
Sellotape brand adhesive tape gives (as far as I can tell) a perfect
90 degree twist for optical frequencies. Two layers of it give
a 180 degree twist. (Now, since all the rebit arrows are double-
ended, a 180 degree rotation won't make any difference no matter
which way the rebit is pointing. We can leave it out, and it won't
make any difference.)
So in the quantum version, we have four boxes that do the following:
0: No rotation, even number of reflections
1: 180 degree rotation, even number of reflections
x: No rotation, odd number of reflections
NOT x: 180 degree rotation, odd number of reflections
If you're familiar with matrix notation, these are
=> | 1 0| 1 => |-1 0| x => | 1 0| NOT x => |-1 0|| 1| |-1| |-1| | 1|
or, most concisely
f => |-1^f(0) 0|
| [itex]-1^f(1)|
If we choose a horizontal or vertical double-ended arrow, we won't
be able to tell if it was reflected: they're both symmetric
horizontally and vertically. These rebits correspond to the
classical inputs zero and one, and as before, we gain no
information about which function it is. However, if we choose a
diagonal arrow, then Bob's our uncle.
Deutch's algorithm, then, goes like this:
1. Start with light polarised in the absorbing direction.
2. Turn the black box so the light goes in diagonally.
3. Shine the light that comes out of the black box through our
polariser into our eyes. If we don't see any light, it's a
constant function; otherwise it's a balanced function.
4. How to make it
You can build a black box by making a device that lets you choose
an even or odd number of reflections while keeping the input and
output angles the same. It takes three mirrors and some cardboard.
The box should look like this:
+---------------------+
| /| /| /| || || || || || || / /|| / / ||/ / |
+ ------------------+
The mirrors in the input and output corners should swivel between 45
degrees and 67.5 degrees. That gives two possibilities: at 45
degrees, we get light entering one port, bouncing to the mirror in
the near corner, then to the mirror in the far corner, and then out.
So at 45 degrees, the light bounces an odd number of times--a
balanced function. At 67.5 degrees, the light takes a path shaped
like three sides of a stop sign: it enters, bounces directly to the
far mirror, and bounces out. In this configuration, the light
bounces twice--a constant function.
If you want to use the phase rotation, make a little frame for the two
layers of sellotape that will fit over one of the ports.
Then with a torch and polarisers on the ports, you'll have yourself a
tabletop quantum computer!
--
Mike Stay
http://www.cs.auckland.ac.nz/~msta039