Visualizing special relativity

The twin paradox

This post is part of a series on visualizing relativity.

As noted in the previous post, special relativity is based on two postulates:

1. The laws of motion are the same in all inertial frames
2. The speed of light is the same in all inertial frames

The conventional view is that we live in a three-dimensional world where time proceeds at a constant rate for all of us independent of motion. But Einstein's theory shows that we instead live in a four-dimensional spacetime where space and time are interdependent. (Note: technical terms are explained in the Glossary at the end of this post.)

Lewis Carroll Epstein in his book Relativity Visualized presents a myth for intuitively understanding the special theory of relativity. As he puts it:

Why can't you travel faster than light? The reason you can't go faster than the speed of light is that you can't go slower. There is only one speed. Everything, including you, is always moving at the speed of light. How can you be moving if you are at rest in a chair? You are moving through time. (pp78-79)

So, according to the myth, each of us are always travelling at the speed of light through 4D spacetime. Since Alice is always at rest with respect to herself, that sets her time direction. The three directions perpendicular to her time direction are the space directions that she perceives. If Alice changes her velocity, she rotates in spacetime such that she is now at rest with a new time direction.

When Bob is travelling at close to the speed of light, Alice measures Bob as aging slowly (time dilation) and shortened in the direction of motion (length contraction). This is simply the effect of Bob being rotated in spacetime relative to her and then projected onto Alice's coordinate system. But in Bob's (at rest) reference frame, his wristwatch is running normally and his shape and size are normal. This is analogous to how a round table appears oval when viewed from an angle. However the difference with relativity is that the projection is not simply perceptual, but is the outcome of collecting measurements from local observers who use clocks and rulers.

Alice's measurements of Bob from her rest frame can be represented by an Epstein spacetime diagram [1] as shown in Figure 1 below.

Figure 1: Bob is travelling at 0.6 times the speed of light in space (relative to Alice)

Alice's proper time is on the vertical axis, while her space dimension is perpendicular to it on the horizontal axis (note: only the x-space dimension appears - the y-space and z-space dimensions are omitted). A radius represents 1 light year in a particular direction - vertical (for Alice at rest), horizontal (for a photon) or an intermediate direction (for Bob).

Alice travels 0 light years in space and 1 light year in time, i.e., she ages 1 year. At the other extreme, a photon travels 1 light year in space and 0 light years in time, relative to Alice.

According to Alice's measurements, Bob travels 0.6 light years in space. Bob's proper time can be calculated using the Pythagorean Theorem (where coordinate time is the length of the red arrow - Bob's worldline, Bob's proper time is the spacetime interval, and coordinate space is the distance Bob has traveled according to Alice's measurements): [1]

coordinate time² = Bob's proper time² + coordinate space²

Solving for Bob's proper time, where the coordinate time (the length of Bob's arrow) is 1:

Bob's proper time = √(coordinate time² - coordinate space²)
                  = √(1² - 0.6²)
                  = √(1 - 0.36)
                  = √(0.64)
                  = 0.8 years (or 9.6 months)

Since Bob has only traveled for 0.8 years at a velocity of 0.6c, the distance he has traveled in his rest frame is less than 0.6 light years. Bob's distance (according to his measurements) can be calculated using the usual distance formula:

Bob's proper space = velocity * Bob's proper time
                   = 0.6 * 0.8
                   = 0.48 light years

Figure 2: Alice is travelling at 0.6 times the speed of light in space (relative to Bob)

In Figure 2, the same situation is shown, but from Bob's (at rest) reference frame. This is achieved by rotating the coordinate system such that Bob's arrow is on the proper time axis. Note that it is now Alice that has aged 0.8 years relative to Bob's 1 year.

These results may seem contradictory - how could it be that Bob has aged less than Alice in Alice's reference frame, but Alice has aged less than Bob in Bob's reference frame? The reason is that the time measurement that each person does of the other is a projection onto their proper time axis. To demonstrate this geometrically, Alice and Bob's reference frames are superimposed in Figure 3. Each observer is at rest, but measures the other moving obliquely. The symmetry is similar to two boats drifting apart from each other, and each perceiving the other as smaller. However, as noted earlier, the difference with relativity is that the projection is measurable, not merely perceptual.

Figure 3: Alice and Bob's reference frames superimposed - the situation is symmetrical

If Alice and Bob meet up and compare notes, they will find no contradiction, i.e., they will be the same age, or just one will be younger than the other. To understand how this works, suppose that Bob returns to Alice at (very close to) the speed of light. His elapsed proper time will then be 0.8 years compared to Alice's now 1.6 years (since Alice ages a further 0.6 years during the return leg, while Bob does not age at all). Symmetrically, suppose that Alice returns to Bob at (very close to) the speed of light. Her elapsed proper time will then be 0.8 years compared to Bob's now 1.6 years. The opposite results in each case are due to the change in reference frames of the traveler (which is, in effect, an acceleration by the traveler that they themselves are able to detect).

These are instances of the famous twin paradox. An Epstein diagram can also show a more common rendering of the twin paradox, where Bob reverses course at the mid-point of his journey and returns to Alice at the same speed.

Figure 4: The twin paradox

In Figure 4, Bob travels the same total distance as in Figure 1, however this time he travels 0.3 light years on the outward journey and 0.3 light years on the return journey (in Alice's frame). As with the example above of Bob returning at the speed of light, Bob ages 0.8 years while Alice ages 1 year.

Figure 5: Alice measures the contracted length of Bob's rocket

In Figure 5, Alice and Bob are part of the way along their respective journeys (note: the solid blue and red arrows are the same length), with the lengths of their respective rockets shown (exaggerated to be visible). Since Bob is traveling relative to Alice, Alice measures Bob's rocket to be shorter than its proper length, as projected on her spatial axis. For example, suppose the proper length of Bob's rocket is 0.1 light years. To calculate the length contraction, Bob's rocket can be rotated a quarter anticlockwise turn to lie along Bob's proper time axis (the red arrow) and projected onto Alice's proper time axis. Since the rocket is 0.1 times the length of the unit line, its projection against the proper time axis is 0.1 * 0.8 = 0.08. Rotating back, its projection against the space axis is also 0.08 light years. [2]

Bob would similarly measure Alice's rocket to be shorter than its proper length. (To see this, rotate the coordinate system such that Bob's arrow is on the proper time axis - then project Alice's rocket onto the spatial axis.)

In summary, both the time dilation and length contraction of an observed entity can be understood as projections onto the observer's proper time and spatial axes respectively. An entity observed by Alice to be travelling very close to the speed of light would be measured as having almost no elapsed time on its clock and almost entirely length contracted.

--

[1] The most common spacetime diagram is the Minkowski diagram. However I've instead used the Epstein diagram here due to its intuitive representation (for a comparison, see Figure 6 below). An Epstein diagram is a space-proper-time diagram that shows the worldlines of objects traveling below the speed of light (i.e., on timelike, but not lightlike or spacelike paths). The basis for the Epstein diagram is explained below.

The Euclidean metric for calculating the total distance between points in 3 dimensional space is:

d² = x² + y² + z²

This is just an application of the Pythagorean Theorem in a Euclidean space. Of interest here is that if a 1 meter ruler is rotated in space, the x, y and z coordinates can all change, but d will remain invariant.

The Minkowski metric for calculating the total "distance" (i.e., the spacetime interval L) between points in 3+1 dimensional spacetime is:

L² = x² + y² + z² - (ct)²
   = d² - (ct)²

It can also be expressed with an imaginary term:

L² = x² + y² + z² + (ict)²
   = d² + (ict)²

Or, as an alternative convention, the signs can be flipped (omitting the negative sign on L²):

L² = (ct)² - x² - y² - z²
   = (ct)² - d²

Minkowski space is non-Euclidean. Of interest here is that if a 1 meter ruler is rotated in spacetime, the x, y, z and t coordinates can all change, but L will remain invariant. Note that when d increases, so does t.

Rearranging the equation:

(ct)² = L² + d²

Which looks just like the Pythagorean Theorem! The spacetime interval L is a measure of the observed object's proper time (τ), d is a measure of the traveled distance, c is the speed of light (normalized to 1 in this post) and t is the elapsed coordinate time. Thus:

t² = τ² + d²

That is the basis for the Epstein diagram. In essence, Minkowski diagrams represent a hyperbolic equation (τ² = t² - d²) that is the difference of squares, whereas Epstein diagrams represent a circular equation (t² = τ² + d²) that is the sum of squares.

Figure 6 compares the Epstein and Minkowski diagrams for the twin paradox.

Figure 6: Comparison of Epstein and Minkowski spacetime diagrams

Epstein diagrams are visually intuitive and quantitatively correct. For example, on the Epstein diagram, it is clear that Bob has aged less than Alice since his proper time is shown as less than Alice's proper time when they reunite. Also, the worldlines are the same length, representing the same elapsed coordinate time. Compare with the Minkowski diagram where Bob's shorter proper time is shown by a longer worldline than Alice's.

[2] The geometry is explained here. In particular, note the similar right-triangles indicated by the angle φ. These triangles can be rotated such that their hypotenuse lies along Bob's arrow, allowing the shorter side lengths to be projected onto Alice's axes.

Glossary

An inertial frame is a reference frame that is either at rest or moving at a constant velocity (i.e., not accelerating).

Proper time (or rest time) is the time τ as measured by a clock in a rest frame. On an Epstein diagram (see Figure 6), proper time is represented on the y-axis. On a Minkowski diagram, proper time is represented by the worldlines. While Bob's proper time is shorter than Alice's, it's shown as longer on a Minkowski diagram.

Proper space (proper length, space displacement, rest length, or rest space) is the distance d as measured using standard length rods in a rest frame. On both Epstein and Minkowski diagrams, the observer's proper space is represented on the x-axis.

Coordinate time (or observer's time) is the time t of a moving object measured by an observer at rest. Thus it is the same for all objects. On an Epstein diagram, coordinate time is represented by the worldlines (which are the same length on the diagram). On a Minkowski diagram, coordinate time is represented on the y-axis.

Coordinate space (or observer's length, coordinate length, or coordinate distance) is the distance d that a moving object travels as measured by an observer at rest. Thus it is the same for all objects. On both Epstein and Minkowski diagrams, coordinate space is represented on the x-axis.

Spacetime is a mathematical model that fuses the three dimensions of space and the one dimension of time into a single four-dimensional manifold.

The worldline of an object is the path that the object traces in spacetime.

The spacetime interval between two events is the length of the segment of the worldline connecting the two events. It is invariant, which means that everyone measures the same value.

Resources

• Relativity Visualized - book by Lewis Carroll Epstein
• In relativity, length contracts at high speeds. But what’s contracting? Is it distance or space or is there even a difference? - Ask a Mathematician
• Epstein explains Einstein
• Epstein Relativity Diagrams - Michael Weiss at Diagonal Argument
• Twin paradox flash player app (may require a flash plugin or an older browser)
• The Twin Paradox - Michael Weiss (Physics FAQ)

Visualizing Galilean relativity

Figure 1: Galileo's ship

This post is part of a series on visualizing relativity.

In 1632, Galileo gave a famous example of a ship travelling at constant velocity, without rocking, on a smooth sea. His claim was that any observer below the deck would not be able to tell whether the ship was moving or stationary.


In Figure 1, an experimenter releases a ball which drops vertically between time t1 and time t2. Does this imply that the boat must be stationary in the water? No, because if the boat is moving at a constant velocity, the ball will also move with that constant velocity (in the boat's direction of movement) and land in the same place, relative to the boat. Thus the experimenter is unable to tell whether the boat is moving at a constant velocity or is stationary.

This result is captured in the following principle:

Galilean relativity: The laws of motion are the same in all inertial frames

An inertial frame is simply a reference frame that is either at rest or moving at a constant velocity (i.e., not accelerating).

Note, however, that from the reference frame of the water (as indicated by the fish at rest between time t1 and time t2), the ball will follow a curved (parabolic) path. That is a measurable relativistic effect (in the Galilean sense).

Figure 2: Adding velocities

In Figure 2, a train is travelling at 100km/h and Bob (on the train) shoots an arrow at 200km/h toward the target. At the same time, Alice (on the ground) also shoots an arrow at 200km/h toward the target.

According to Alice, the velocity of Bob's arrow is the velocity of the train plus the velocity of the arrow according to Bob. That is, Alice would measure the velocity of Bob's arrow to be 100km/h + 200km/h = 300km/h. Thus Bob's arrow would hit the target before hers, even though both arrows had the same velocity in their respective frames of reference.

Figure 3: Adding velocities (light)

In Figure 3, Bob fires a laser that emits photons travelling at the speed of light (c) toward the target. Alice fires her laser at the same time. Alice, it seems, would measure the velocity of Bob's light to be c + 100km/h, and Bob's laser light hitting the target before hers.

However that is not what happens! Instead, the light from both lasers hits the target at the same instant and Alice measures the velocity of Bob's light to be c, just as Bob does.

This surprising result lead Einstein to extend Galilean relativity to include the following postulate:

The Principle of Invariant Light Speed: The speed of light is the same in all inertial frames

Galilean relativity and the principle of invariant light speed together comprise Einstein's special theory of relativity. As you may know, this gave rise to a number of unexpected consequences, including relativity of simultaneity, time dilation, length contraction and a new equation for adding velocities.

The next post will explore those consequences and present a way to intuitively visualize special relativity.

Visualizing relativity

The principle of relativity

Suppose Alice is standing on a train platform waving her friend Bob goodbye as the train he is on moves away from the platform. From Alice's perspective, she is standing still on the platform while the train is moving away from her. But from Bob's perspective, he is standing still on the train while the platform is moving away from him.

We suppose that Alice and Bob are describing the same situation, as governed by the same laws of nature, but just from a different vantage point. This idea is captured by the principle of relativity:

Principle of relativity: The laws of nature are the same in every frame of reference

In the train example, Alice and Bob each represent a frame of reference. Those reference frames are relative to each other, hence the name of the principle. And the train scenario is governed by natural laws that are invariant across those reference frames.

This series of posts will show various applications of this principle and how to visualize their effects:

• Galilean relativity
• Special relativity
• General relativity

A proof of the Pythagorean Theorem

A 3-4-5 triangle

The Pythagorean Theorem states that the area of the square on the hypotenuse of a right-angled triangle equals the sum of the areas of the squares on the other two sides. Algebraically (where c is the length of the hypotenuse and a and b are the lengths of the other two sides):

    c² = a² + b²

I thought it would be fun to attempt to prove the theorem for myself. This post describes my solution.

Figure 1: Draw a right-angled triangle with squares

1. Draw a right-angled triangle with squares

• Draw a right-angled triangle
• Draw the squares extending from each side
• Label the sides a, b and c.

Figure 2: Flip the square on the hypotenuse

2. Flip the square on the hypotenuse

• Flip the square on the hypotenuse over
• Mark dotted lines to indicate the larger square containing the flipped square [1]

Figure 3: Label the segments

3. Label the segments

• Mark the segments on each side of the dotted square and label as follows:
• Label the top and right segments a and b as guided by the red and green squares
• Mark the top segment on the left side b, since it is the third side of a right-angled triangle with a and hypotenuse c as the other two sides
• Mark the bottom segment on the left side a, since it is symmetrical to the right side
• Mark the right segment on the bottom side a, since it is the third side of a right-angled triangle with b and hypotenuse c as the other two sides
• Mark the left segment on the bottom side b, since it is symmetrical to the top side

4. Do some algebra

• The area of the square on the hypotenuse equals the area of the large square minus the areas of the triangles in the four corners:

    c² = (a + b)(a + b) - 4(a * b / 2)
       = a² + b² + 2ab - 2ab
       = a² + b²


Which is the Pythagorean Theorem!

It turns out that there are over a hundred possible proofs. The above proof is similar to proof #4 which is credited to the 12th century Hindu mathematician Bhaskara II.

--

Figure 4: Side and corner collinearity

[1] Note that the outer sides of the red and green squares are on the dotted lines. That each outer side is collinear with its adjacent yellow square corner is shown by rotating and shifting the original blue triangle to construct the sides of the flipped yellow square.

The square in the center has a side length of (b - a). As an alternative proof, the area of the square on the hypotenuse equals the area of the center square plus the area of the four triangles:

    c² = (b - a)(b - a) + 4(a * b / 2)
       = b² + a² - 2ab + 2ab
       = a² + b²

Visualizing quantum computations

Figure 1: Quantum parallelism

You are presented with an opaque box that has two buttons labelled A and B. Each button is programmed to glow either red or green when pressed. Can you determine, without investigating inside the box, whether the two buttons are programmed to show the same color or different colors?

The answer, of course, can be determined by pressing each button to see what it does. And it is necessary to press both buttons - pressing just one button won't convey enough information to determine the answer.

Figure 2: Black box function

This scenario can be represented in an algorithm using two binary digits (bits) to represent the color that glows when each respective button is pressed. Analogous to the opaque box, the function that retrieves information about the bits is a black box (see Figure 2) where our focus (for now) is on the inputs and outputs. The algorithm is outlined in the following code fragment.

 1: // constant bit definitions
 2: bitButtonIndex { A = 0, B = 1 }
 3: bitColorIndex { red = 0, green = 1 }
 4:
 5: // black box function declaration
 6: f(input bitButtonIndex) output bitColorIndex;
 7:
 8: bitColorForButtonA = f(A);
 9: bitColorForButtonB = f(B);
10: if (bitColorForButtonA == bitColorForButtonB) then
11:   bitButtonsShowTheSameColor = yes;
12: else
13:   bitButtonsShowTheSameColor = no;

The important thing to note about the above is that the black box function needs to be called twice to determine whether the buttons show the same color.

This same scenario can also be represented on a quantum computer. However in this case the black box function accepts a qubit as input containing the button information and returns a qubit as output containing the color information. The quantum algorithm is outlined in the following code fragment.

 1: // quantum black box function declaration
 2: Uf(input/output qubitX, qubitY); // |x,y> -> |x,y⊕f(x)>
 3:

 4: // variable declarations

 5: qubit x;  // x holds button or (later) color information
 6: qubit y;  // y facilitates use of the black box function
 7:
 8: x = |0>;  // prepare x in a known state

 9: H(x);     // transform x to |+>, i.e., 1/√2(|0> + |1>)

10:
11: y = |0>;  // prepare y in a known state

12: X(y);     // flip state of y to |1>

13: H(y);     // transform y to |->, i.e., 1/√2(|0> - |1>)

14:

15: Uf(x, y); // transform x to |+> or |->

16. H(x);     // transform x from |+> to |0> or from |-> to |1>

17:

18: bitMeasurementResult = M(x); // measure the value of x
19: if (bitMeasurementResult  == 0) then
20:   bitButtonsShowTheSameColor = yes;
21: else
22:   bitButtonsShowTheSameColor = no;

Note that the quantum black box function only needs to be called once to determine whether the buttons show the same color. While the classical function only processes a single specific button at one time, the quantum function can process both button indexes simultaneously. This is represented by the (superposed) state of x as 1/√2(0> + |1>) prior to the call to Uf, where 0 and 1 have the same meaning as per the classical algorithm (i.e., as button indexes for A and B respectively).[1]

Before going into the details of the above code, this algorithm (called Deutsch's Algorithm) is probably the simplest example demonstrating the parallelism of quantum computing - the ability to evaluate all possible inputs to a function simultaneously. Qubits can also be combined to exponentially increase the parallelism. For example, Figure 1 shows a single four-bit input that is processed by a classical computer to produce a single four-bit output. Compare that to the four-qubit input that allows up to 2⁴, or 16, superposed values to be input and then simultaneously processed by a quantum computer to produce 16 superposed values as output.

But there is a major problem! If the qubit returned by the quantum function is in superposition and it is measured, then the superposed state randomly collapses to just one of the two basis states (|0> or |1>) - a single bit of information! So the quantum function needs to encode the answer to our final question such that it can be successfully extracted by a measurement. While quantum computing promises exponential speedup and memory efficiencies, the challenge is to construct algorithms that amplify the right answer and cancel out wrong answers such that the right answer will be measured with high probability.

In fact, this is what the above algorithm is able to do. Note that unlike the classical algorithm, the black box function does not return the colors associated with the specific buttons. Instead, the function returns a result that represents the relative difference in the button colors (if any), whatever those colors happen to be.

Figure 3: Quantum circuit for Deutsch's Algorithm

Now let's turn to the details of the quantum algorithm. The circuit for this algorithm is illustrated in Figure 3. The circuit shows qubit x on the top wire and qubit y on the bottom wire as they are transformed over time (from left-to-right). In quantum mechanics, the functions (or logic gates) are unitary which means, among other things, that they are reversible. Note that the black box function (also termed a quantum oracle) specifies y⊕f(x) as an output. The ⊕ symbol represents an exclusive or (xor) operation.

Per line 9, input x is in state 1/√2(|0> + |1>), representing a superposition of pressing button A and pressing button B. Recall that 0 represents button A and 1 represents button B. If button A glows green, a 180° phase change is applied to state |0>. Similarly, if button B glows green, a 180° phase change is applied to state |1>. This can be expressed by the following formula (derived in [2]) where f is the original classical black box function:

1/√2((-1)^f(0)|0> + (-1)^f(1)|1>)

This reduces to one of the four output states in the following table which can then be changed back to the computational basis state with a Hadamard transform. Note that the measurement ignores the global phase (i.e., the leading minus signs).

Btn A   Btn B  |                                       Same
 f(0)    f(1)  |     Output x      Hadamard   Measure  color?
---------------+---------------------------------------------
red:0   red:0  |   1/√2(|0> + |1>)    |0>        0      yes
grn:1   grn:1  |  -1/√2(|0> + |1>)   -|0>        0      yes
red:0   grn:1  |   1/√2(|0> - |1>)    |1>        1      no
grn:1   red:0  |  -1/√2(|0> - |1>)   -|1>        1      no

Note that the phase change formula and the color results are a mathematical representation of what is occurring within the quantum black box function. While we can measure the output qubit, we cannot access the specific button color information (which is encoded in the phase of the states). Nonetheless the information we can access is sufficient to determine whether the colors are the same.

Figure 4: MZI with a glass sample representing the
color green when button A is pressed

Our original scenario can be modified to utilize quantum parallelism by using a Mach-Zehnder interferometer as our quantum black box. When the paths of the MZI are equal in length (and no samples are present), a photon entering the MZI (and travelling in a superposition of both paths) will always end up at detector 1. To model our scenario, the upper path will represent the pressing of button A while the lower path will represent the pressing of button B. A glass sample placed on either or both of the paths will represent the color green while its absence will represent the color red. The thickness of the glass sample is such that it will change the phase of the photon passing through it by 180°.

The effect of placing a sample on just one of the paths is that the interference at the final beam splitter will result in the photon always ending up at detector 2. Placing a sample on both paths means the photon will accumulate identical phase changes on each path which cancel out. So the effect is that the photon will always end up at detector 1 just as it would when there are no samples present. The glass samples thus implement the exclusive or (xor) operation in our quantum black box. While we are not able to determine the specific colors of the buttons (without investigating inside the black box), we can determine whether the colors are the same or not by observing which detector the photon arrives at.

References:

• Blog post on visualizing qubits
• Blog post on modeling quantum interference
• Quantum Algorithm with an example - Jonathan Hui
• Lecture on the Deutsch Algorithm - Scott Aaronson
• Q#: A Quantum Programming Language by Microsoft
• Simulating a Quantum Computer with a Mach-Zehnder Interferometer - Frank Rioux

"Suppose you are asked if two pieces of glass are the same thickness. The conventional thing to do is to measure the thickness of each piece of glass and then compare the results. As David Deutsch pointed out this is overkill. You were asked only if they were the same thickness, but you made two measurements to answer that question, when in fact it can be done with one." - Frank Rioux

--

[1] The coefficient of 1/√2 is the probability amplitude which, when squared, gives the probability of measuring the associated state. In this case, there is a 1/2 probability of measuring 0 and a 1/2 probability of measuring 1.

[2] The quantum black box function maps |x,y> to |x,y⊕f(x)) where ⊕ symbolizes xor. The input qubits to the function are:

|x> = 1/√2(|0> + |1>)
|y> = 1/√2(|0> - |1>)

Combining the two inputs (where ⊗ symbolizes the tensor product):

|x,y> = 1/√2(|0> + |1>) ⊗ 1/√2(|0> - |1>)
      = 1/2(|0> + |1>)(|0> - |1>)
      = 1/2(|0>(|0> - |1>) +
            |1>(|0> - |1>))

Substituting y⊕f(x) for y:

|x,y⊕f(x)> = 1/2(|0>(|0⊕f(0)> - |1⊕f(0)>) +
                   |1>(|0⊕f(1)> - |1⊕f(1)>))

When f(x) = 0 (indicating red), the state remains unchanged. When f(x) = 1 (indicating green), the sign is flipped. This effect on the phase can be represented as (-1)^f(x) giving (-1)⁰ = 1 and (-1)¹ = -1 respectively. Continuing:

            = 1/2(|0>((-1)^f(0)|0> - (-1)^f(0)|1>) +
                  |1>((-1)^f(1)|0> - (-1)^f(1)|1>))
            = 1/2((-1)^f(0)|0>(|0> - |1>) +
                  (-1)^f(1)|1>(|0> - |1>))
            = 1/2((-1)^f(0)|0> + (-1)^f(1)|1>)(|0> - |1>)
            = 1/√2((-1)^f(0)|0> + (-1)^f(1)|1>) ⊗ 1/√2(|0> - |1>)

So the separate output qubits of the quantum black box function are:

|x> = 1/√2((-1)^f(0)|0> + (-1)^f(1)|1>)
|y> = 1/√2(|0> - |1>)

Note: The reversible xor operation is implemented using a CNOT gate. When applied in the computational basis { |0>,|1> }, x is the control qubit and y is the target qubit. However when applied in the Hadamard basis { |+>,|-> } as above, y becomes the control qubit and x becomes the target qubit, as explained here.

Visualizing qubits

Figure 1: Classical and quantum bits

In classical computing, the basic unit of information is the bit (or binary digit). As illustrated in Figure 1, a bit can be in one of two states as represented by the values 0 and 1. [1] This can be physically implemented in various ways such as by two distinct voltage levels in a circuit or by a switch. As the basic unit of information, the bit abstracts over the physical implementation, allowing the programmer to work with that abstraction rather than the details of the underlying hardware and physics.

In quantum computing, the basic unit of information is the qubit (or quantum bit). When a qubit is measured (a read operation), it exhibits the same characteristics as a classical bit. That is, a value of 0 or 1 is returned. This is illustrated in Figure 1 by the points at the north and south poles of the sphere. However, as suggested by the sphere visualization, the state of a qubit is very different to the state of a classical bit. As well as being in a state of 0 or 1, a qubit can also be transformed into a superposition of those two states which is represented by a point elsewhere on the surface of the sphere.[2]

Figure 2: Qubit vector space
(imaginary dimensions omitted)

But set aside the sphere visualization for the moment. In quantum computing, the state of a qubit is represented by a vector in a vector space. The vector space is two dimensional with the two standard basis vectors representing the values of 0 and 1 (see Figure 2, where the basis vectors are denoted in ket notation as |0> and |1>).  The state of the qubit can be one of the two basis vectors or a linear combination of both and is denoted as |ψ> (psi). The length of the vector is always 1 (i.e., terminating on the unit circle). Finally, the vector space is complex rather than real which means the coefficients α and β of the basis states are complex numbers. In ket notation, this would be:

|ψ> = α|0> + β|1>

Note that each complex number has two degrees of freedom (i.e., a complex number has a real component and an imaginary component) for a total of four degrees of freedom. The 2D Cartesian plane in Figure 2 shows only the real components of α and β.

Figure 3: The Bloch sphere

However it is possible to do better. Note that the length of |ψ> must always be 1. That is, |α|² + |β|² = 1. This removes one degree of freedom. In addition, only the relative difference between the complex phases of the states has observable consequences. For example, if one state has a phase of π/2 and the other a phase of 3π/2, the relative difference around the complex plane is π. So this removes another degree of freedom leaving just two degrees of freedom. It is now possible to visualize the state of the qubit on the surface of a sphere (called the Bloch sphere). In Figure 3, |ψ> is represented by a vector (orange) radiating from the center of the sphere to a point on the surface. The latitude is designated by the polar angle from the Z-axis (θ or theta) and the longitude is designated by the azimuthal angle from the X-axis (φ or phi).

In the Bloch sphere representation, the basis states |0> and |1> are shown at the north and south poles. When a measurement is performed on the qubit, the vector |ψ> collapses to one of the two basis states and a value of 0 or 1 is measured. The closer the point is to one of the poles, the more likely that a measurement of the qubit will collapse the state to that pole. More precisely, the probability that a particular value is measured is the square of the coefficient for that state.[3] The state coefficients can be calculated from the angles as follows:

α = cos(θ/2)
β = e^iφ sin(θ/2)

where e^iφ is the physically significant relative phase. In effect, the XY plane is the complex plane that locates the phase while the position along the Z-axis indicates the probability of measuring a particular state.[4]

The vector |ψ> is moved to new locations on the sphere via rotations around the X, Y and Z axes. To rotate around an axis, the following Pauli matrices are used:[5]

X = [0 1]   Y = [0 -i]   Z = [1  0]
    [1 0]       [i  0]       [0 -1]

Other rotations include the Hadamard matrix and the Phase shift matrix:

H = 1/√2[1  1]   S = [1 0]
        [1 -1]       [0 i]

These matrices transform between the different Pauli-basis states, i.e., H: {|0>,|1>} to {|+>,|->} and S: {|+>,|->} to {|+i>,|-i>}. [6] As an example, suppose the the qubit is prepared in state |0>. Applying the Hadamard matrix gives:

|ψ> = 1/√2[1  1][1] = 1/√2[1] = 1/√2(|0> + |1>)
          [1 -1][0]       [1]

This represents a superposition where |ψ> is located at the point denoted by X on the sphere (the |+> state). The square of the amplitude for each state is 0.5 so, if a measurement is taken, there is a 50% probability of measuring 0 or 1. Applying the Phase shift matrix gives:

|ψ> = [1 0][1/√2] = 1/√2[1] = 1/√2(|0> + i|1>)
      [0 i][1/√2]       [i]

This represents a superposition where |ψ> is located at the point denoted by Y on the sphere (the |+i> state).

To visualize the qubit states for different angles, try the Bloch sphere simulator.

To summarize so far, a qubit can contain a seemingly unlimited amount of information since the point on the Bloch sphere representing the qubit state can be extremely fine-grained. However the information extracted by a measurement is always 0 or 1 (with the probability depending on the latitude of the point on the sphere).

Now consider the combination of multiple qubits. While a 2-bit system can hold only one value between 0 and 3 (2² - 1) at one time, a 2-qubit system can hold all 4 values in superposition at the same time. This provides an exponentially larger computation space with computations able to be performed on all the values in parallel. For a sense of what this means, consider that a 300-qubit system in superposition provides 2³⁰⁰ simultaneous values - more than the number of atoms in the observable universe.

For a 2-qubit system, a superposition is produced by preparing both qubits in the |0> state and then applying a Hadamard gate, as follows:

|ψ> = H|00>
    = 1/√2(|0> + |1>) ⊗ 1/√2(|0> + |1>)
    = 1/2(|00> + |01> + |10> + |11>)

This is called a separable (or unentangled) state because the composite system is separable into two subsystems (i.e., one for each qubit) as the second line indicates.[7] In this case, if one of the qubits were measured then the other qubit value could still be either 0 or 1 since the two qubits are independent.

Figure 4: Preparing a Bell state

Alternatively, a maximally entangled state, called a Bell state, can be produced by preparing both qubits in the |0> state and then applying a Hadamard gate to the first qubit (and an Identity gate to the second qubit) and a CNOT gate [8] to both qubits, as follows:

|ψ> = CNOT (H⊗I)|00>
    = CNOT 1/√2(|0> + |1>)|0>
    = 1/√2(|00> + |11>)

The two qubits are no longer independent of each other. In this case, if one of the qubits were measured, then the other qubit would have the same value when measured.

To solve a problem on a quantum computer, interference between states needs to be exploited to amplify signals leading to the right answer and cancel signals leading to the wrong answer. This requires designing algorithms that exploit specific features of the problem such that when the system is measured, the desired answer is obtained.

--

[1] Or a similar two-state representation such as true and false or on and off.

[2] As with a classical bit, a qubit can also be physically implemented in various ways, such as by the ground and excited states of a particle or by the spin-up and spin-down states of a particle.

[3] This is the Born rule.

[4] The states α|0> + β|1>, α|0> − β|1> and α|0> + iβ|1> all have the same measurement probabilities in the standard basis. However they are distinct states due to their phase differences and therefore behave differently in terms of how they evolve. Also, the probabilities can differ when measured in a different basis.

[5] Recall that

|ψ> = cos(θ/2)|0> + e^iφ sin(θ/2)|1>

X = [0 1]   Y = [0 -i]   Z = [1  0]
    [1 0]       [i  0]       [0 -1]

The Pauli matrices X, Y and Z give rise to the rotation operators about the x, y and z axes of the Bloch sphere:

R_x(θ) = e^-iθX/2 = [ cos(θ/2)     -i.sin(θ/2) ]
                  [ -i.sin(θ/2)  cos(θ/2)    ]
R_y(θ) = e^-iθY/2 = [ cos(θ/2)     -sin(θ/2)   ]
                  [ sin(θ/2)     cos(θ/2)    ]
R_z(θ) = e^-iθZ/2 = [ e^-iθ/2        0            ]
                  [ 0             e^iθ/2         ]

[6] The basis states corresponding to each axis (illustrated in Figure 5) are:

X: 1/√2(|0> + |1>),1/√2(|0> - |1>) or |+>,|-> (the diagonal or plus-minus basis)

Y: 1/√2(|0> + i|1>),1/√2(|0> - i|1>) or |+i>,|-i> (the circular or right-left basis)

Z: |0>,|1> (the up-down, standard or computational basis)

Figure 5: Basis states for each axis

[7] V ⊗ W represents the product of two vector spaces, itself a vector space.

[8] The CNOT gate flips the second qubit (the target qubit) if and only if the first qubit (the control qubit) is |1>.