A very good, truly gentle intro to quantum computing. A basic understanding of probability and complex numbers is required. But, if you’re truly interested in gaining a basic understanding of QC’s mathematics, you’ll likely already be familiar with those.

ABSTRACT: Quantum Computing is a new and exciting field at the intersection of mathematics, computer science and physics. It concerns a utilization of quantum mechanics to improve the efficiency of computation.Here we present a gentle introduction to some of the ideas in quantum computing. The paper begins by motivating the central ideas of quantum mechanics and quantum computation with simple toy models. From there we move on to a formal presentation of the small fraction of (finite dimensional) quantum mechanics that we will need for basic quantum computation. Central notions of quantum architecture (qubits and quantum gates) are described. The paper ends with a presentation of one of the simplest quantum algorithms: Deutsch’s algorithm. Our presentation demands neither advanced mathematics nor advanced physics.

In their frequent shopping sprees Paris and Nicole often have trouble checking the bill. To address their less than impressive numeracy skills they decide to return to school. After a year of maths training the teacher wants to test the class of 25 students and lines them up in a queue such that Paris and Nicole are standing next to each other. The teacher then writes a whole number on the board and the first person in the queue says “That number is divisible by 1.” Then the second person in the queue says “That number is divisible by 2,” and so on till the final student in the queue says “That number is divisible by 25.” After all this the teacher exclaims “Well done! Except for Paris and Nicole everyone made a correct statement.” Find where Paris and Nicole were standing in the queue.

So, we’re looking for a number that can be divided by all numbers from 1 through 25 EXCEPT two of them, that are also consecutive. The number 1 will divide anything, so, that’s trivial. We can also come up with a number that can be divided by ALL of the numbers by simply taking the product of all of those numbers. This doesn’t quite give us our answer, and it also results a number that is much bigger than we really need since some factors would be repeated. (e.g. any number for which 4 is a factor will also have 2 as a factor, so if we don’t need to include both 4 (i.e. 2 x 2) and 2 as factors. Take this a bit further, you see that by including 16 as a factor (2 x 2 x 2 x 2) we include 2, 4, and 8 as well.)

Let’s create such a product, expressed in a form that is prime-factored, though assuming all of the students’ answers were correct:

2: prime
3: prime
4: 2 x 2
5: prime
6: 2 x 3
7: prime
8: 2 x 2 x 2
9: 3 x 3
10: 2 x 5
11: prime
12: 2 x 2 x 3
13: prime
14: 2 x 7
15: 3 x 5
16: 2 x 2 x 2 x 2
17: prime
18: 2 x 3 x 3
19: prime
20: 2 x 2 x 5
21: 3 x 7
22: 2 x 11
23: prime
24: 2 x 2 x 2 x 3
25: 5 x 5

Combining these (e.g. the factored forms of 4 and 8 are implicit in the factorised 16) we get

2 x 2 x 2 x 2 x 3 x 3 x 5 x 5 x 7 x 11 x 13 x 17 x 19 x 23 = 26771144400.

This number is divisible by all of the numbers from 1 to 25. It should be easy to see that by removing, say, 13, we get a number that is still divisable by all of the other numbers from 1 through 25. (13 x 2, the smallest of the other numbers, equals 26, which falls outside range of factors.) Removing 13 we get

2 x 2 x 2 x 2 x 3 x 3 x 5 x 5 x 7 x 11 x 17 x 19 x 23 = 2059318800,

But, we need TWO CONSECUTIVE numbers. Suppose we stick with 13 and try removing 12 as well. But, 12 = 2 x 2 x 3, so, we’d have to either remove both of the 3’s as factors, or at least 3 of the 2’s to have no 12. Suppose we remove both 3’s to give us

2 x 2 x 2 x 2 x 5 x 5 x 7 x 11 x 17 x 19 x 23

Now we’d have no 13, no 3, no 6, no 9, no 15 … already we have more than two numbers that don’t divide whatever was written on the board. So, 12 won’t work. How about 14? Same problem. You’d need to remove either all of the 2’s or the 7, but, removing all of the 2’s gets rid of all even numbers as valid factors, and removing the 7 gets rid of 14 and 21 as well. So neither Paris nor Nicole occupy the 13th place in line.

Let’s try 17. Like 13, when you remove this as a factor from the original factorization, above, you get a number that is divisible by all other numbers except for 17. We then need to look at 16 and 18 as possible second candidates. 16 = 2 x 2 x 2 x 2. Take out just one of those 2’s and we can still keep every other product in which 2, 4, or 8 is a factor, so removing just one 2 results in the loss of only 16 as a factor. Looks like Nicole and Paris were the 16th and 17th students in the line. For completeness we can look at 18 and see that it doesn’t work since 18 = 2 x 3 x 3, so we’d need to drop all of the 2’s which means we’d have a product with more than two wrong answers in the list.

So, our answer is

2 x 2 x 2 x 3 x 3 x 5 x 5 x 7 x 11 x 19 x 23 = 787386600.

To see if I got the right answer, I googled the problem and found this site (page 3) with the exact same problem and a solution. They get the same places for Paris and Nicole as I did (16 & 17) but their number (that the teacher wrote on the board) is different: 2362159800. This looks like it’s about 3 times what my answer is, and in fact it is exactly 3 times my answer. In other words, they have an extra “3” in their factorization, for whatever reason. So, both answers are correct, but mine is the SMALLEST number that is a factor of all numbers from 1 through 25 excepting 16 and 17.

This little puzzle popped up the other day and I thought it would make a good, simple example of how to deal with square roots.

First, a little terminology: The word for root in latin is radix from which we get words like radius and radical. Mathematicians refer to the square root symbol √ as the radical symbol, and the stuff we’re taking the square root of they’ll refer to as what’s under the radical.

We start with this.

We can get rid of square root symbols by just squaring what’s under them, which will leave just the terms under the radical and nothing else. Since this is an equation, we’ll need to do this to both sides:

When we multiply this out, it looks like a real mess:

We can combine the two x’s to make this

But, it isn’t all that much simpler. Let’s try another approach. Having two different radicals on the same side of the equation is what makes this messy, so, let’s move one of them to the other side of the equals sign. We can move the term by subtracting it from both sides.

Now let’s square both sides of the equation like we did before and see what we get:

I know, it doesn’t look all that much simpler, but, notice how there is a solitary x term on both sides? We can get rid of that by subtracting x from both sides:

leaving us with

It’s looking easier already! Let’s subtract 15 from both sides, and then add to both sides. We get

Now we have simple terms for both left and right hand sides of the equation. Divide both sides by 30 to get

Square both sides (yes, again) to get rid of the radical, and we end up with

Let’s see if this is right. Plug 49 in for x in the original equation:

We can add the 49 and 15 under the first radical to get

The square root of 64 is 8 (8 x 8 = 64) and we already have square root of 49 being 7, so

For the third time in a century we have another election in which the candidate who won the popular vote did not gain enough electoral votes to win the presidency. This probably leaves you scratching your head, wondering how that’s even possible? After all, the number of electors each state has is based on the size of that state’s population, right? If a candidate gets the most votes in that state, that candidate wins all of the electors for that state. If you sum up all those votes the winning candidate should have the biggest total in both the popular vote and the electoral vote counts. Right? Yet, we have two recent examples where the candidate who won the popular vote LOST the electoral vote. (Gore in 2000, and Clinton this year.)

You don’t need to have a degree in math or political science to understand how this can happen. It looks complicated because there are so many states involved and the outcomes in those states are determined not just by votes cast, but by the percentage of voters who actually vote. If we look at a simpler system, and just assume everyone who can vote does, electoral math – and weird outcomes like we’ve just seen – are much easier to understand.

An Example

Let’s imagine a country that has just 6 states. One state has a population of 100, the other five have populations of 10 each. Each state is allotted one electoral vote for every 10 people. (We round up to the next 10, so a state with 13 people would be treated as though it had 20 and thus get 2 electoral votes.) Electors are awarded on a winner-take-all basis: whoever wins the most votes in that state, even if only by a single popular vote, wins all of the electoral votes.

State

Population

Electors

Big State

100

10

Small State 1

10

1

Small State 2

10

1

Small State 3

10

1

Small State 4

10

1

Small State 5

10

1

Now, suppose you have an election to decide between candidate Jim and candidate Nancy for the next president. Even if all of the Small States vote unanimously for Jim, giving him 50 popular votes, he’ll only get 5 electoral votes. But if Jim loses in the Big State, even by only a few votes, Nancy gets all 10 of that state’s electoral votes, and thus beats Jim. All Nancy needs to do to win is get 51 votes (Jim would presumably get the other 49.)

Candidate

Big State Tally

Small State Tally

Popular Total

Electoral Total

Nancy

51

0

51

10

Jim

49

50

99

5

Nancy’s electoral tally is 10, but Jim’s is only 5. Yet, the popular vote CLEARLY favored Jim, giving him a total of 99 (50 from the Small States plus 49 from the Big State) with Nancy only receiving 51. Nancy wins with the most electoral votes even though she lost the poplar vote. Jim could lose by a very wide margin in the Big State — as much as 26 to 74 — and still win the popular vote (76 to 74), but lose the electoral college the way we’ve laid this out. This system is quite obviously biased in favor of the state with the most (voting) people.

Unbiasing the Bias

Let’s see if we can fix that the same way representation in the US’s legislative branch (Congress) was fixed. We’ll start by giving every state just one more electoral vote. We end up with Big State having 11 votes and each Small State having 2. Together the small states have 10 votes, which is better than before but still not enough to overcome Big State’s voting “power”.

So, let’s give every state two additional electoral votes and see what happens.

State

Population

Electors

Big State

100

12

Small State 1

10

3

Small State 2

10

3

Small State 3

10

3

Small State 4

10

3

Small State 5

10

3

Now each Small State has 3 electoral votes for a total of 15, and the Big State has 12. Recalculating the tallies …

Candidate

Big State Tally

Small State Tally

Popular Total

Electoral Total

Nancy

51

0

51

12

Jim

49

50

99

15

Nancy now has 12 electoral votes, but Jim has 15, so Jim wins both the popular vote and the electoral college. We can all agree this is a fair and decisive outcome.

Or, is it?

In fact, this doesn’t eliminate the bias at all; it just shifts it to the smaller states. Sure, it gives the Big State 20% more voting “power”, but it gives each of the Small States 200% more voting power.

Let’s go back to our example and change the vote counts so that Nancy gets 80 votes in the large state and Jim only 20. Nancy still gets no votes in the Small States like before and Jim gets all of the popular votes there and so wins those electoral votes.

Candidate

Big State Tally

Small State Tally

Popular Total

Electoral Total

Nancy

80

0

80

12

Jim

20

50

70

15

Nancy wins the overall popular vote with a tally of 80 to Jim’s 70 (20 from Big State plus 5 x 10 from the Small States), but loses the electoral college to Jim with only 12 votes to his 15. In fact, Nancy could completely trounce Jim in the Big State, even winning it unanimously in the popular vote, and get 4 votes in every small state, giving her a whopping 120 votes to Jim’s 30. Jim would still win the most electoral votes and thus win the election.

A more recent, up-close-and-personal example

Our example isn’t all that far off from what the electoral map actually looked like in the first US election, held in 1788^{1}. In that election, John Hancock (Federalist) soundly defeated George Clinton (anti-Federalist). This map shows how the distribution of slave states and free states or industrial vs agrarian states was more or less even for both candidates. Worth noting, 51 out of the 96 total electoral votes rested with just 5 of the `13 states. That is, more than half the electoral college — clearly enough to carry any election — rested with less than half of the states. If electoral votes were simply one-state-one-vote, the 8 smaller states would have the greater power. Left to a one-(land-owning)-man-one-vote system, the more populous states have the upper hand. Rather than pick one or the other, the Framers of the Constitution came up with a system that combined these two extremes.

In the 2016 election cycle, Donald Trump won the most electoral votes and thus won the presidency even though Hillary Clinton won the popular vote by nearly three million more than Trump. Let’s look at how electoral math figured into this by looking at one of the two, electorally-large blue bastions, New York, which has 29 electoral votes, and a handful of small (by population), red states that have a total of 29 electoral votes between them. The following table^{2} depicts just such a collection.

Red State

Clinton

Trump

Electoral

Idaho

189,765

409,055

4

Iowa

653,669

800,983

6

Montana

177,709

279,240

3

Nebraska

284,494

495,961

5

South Dakota

117,548

227,721

3

West Virginia

188,794

489,371

5

Wyoming

557,93

174,419

3

Totals

1,667,772

2,876,750

29

Both the popular vote and electoral vote tallies indicate Trump to be the clear winner among these states. New York, on the other hand went unambiguously for Clinton with 4,547,562 votes to Trump’s 2,814,589. Clinton absolutely demolished Trump in New York’s popular vote and thus gained its 29 electoral votes. But, take a look at what happens when you add the New York popular vote with that of the red states:

State(s)

Clinton

Trump

Blue (NY)

4,547,562

2,814,589

Red

1,667,772

2,876,750

Totals

6,215,334

5,691,339

In the overall totals, Clinton wins over half a million more votes than Trump in this subset of states — a margin of about 4.4% — yet they come out dead even in the electoral count.

Let’s throw in just one more small red state — Alaska, for example, which has only three electoral votes — Clinton still beats Trump by nearly half a million votes, yet loses the electoral count 32 to 29. Or, try this with Maine, which splits its electoral votes: Two went to Clinton, one to Trump. Clinton wins this electoral match-up by just one point, which hardly reflects the popular tally in which she wins by over a half million.

What are those “bonus” electoral votes really worth?

Suppose we paired up as many red and blue states as we could and subtracted two electoral votes from each of these states. In our example (before throwing in Alaska), we would discount New York’s two “bonus” electoral votes along with another two votes from one of the red states. That leaves 12 bonus from the other six red states. Now, divide the difference in the popular vote count (around 500,000) by these remaining 12 electoral votes and you find that they are worth just under 44,000 popular votes EACH. (This number would vary, of course, depending on actual voter turn out in a given election.) In other words, without this electoral bonus, for Trump to have matched Clinton in terms of the popular vote in these red states, he would have had to win an additional 87,000+ votes in each state, on average. If you subtract that number from the vote tallies for Trump in each of the red states and then recalculate the totals (including New York), Clinton beats Trump by more than a million popular votes, yet still ties him in the electoral count, 27-27^{3}.

I said on average rather generously. In fact, electoral votes aren’t “averaged”, so if we want to be truly strict about this, we’ll insist that Trump would have needed at least 87,000 more votes per state, for each of those six states. Where the popular margin was clearly in his favor, as it was in this sample, he still wins both the popular and electoral counts. If we include Alaska and apply this arithmetic, we have roughly 34,000 popular votes per bonus electoral vote. Subtracting twice this number (~68,000) as we did before, from Alaska’s popular count for Trump actually has Clinton winning Alaska in both the popular vote and electoral counts, 30-27.

If we apply this same arithmetic to all 50 states, Trump’s electoral edge of 77 electoral votes versus Clinton’s popular margin of 2,865,075 means each of those “bonus” electoral votes had the equivalent of 37,200 popular votes for Trump. Since he didn’t have to actually win those votes, he in effect won the election at a discount of sorts.

Is there a better way?

One solution that is regularly (and often) proposed is to do away with the electoral college completely and have just a popular vote. This would work fine when there is a clear choice or when a large enough part of the electorate is behind one of the candidates to make the vote clearly decisive. When voters are more or less evenly split, the system becomes highly vulnerable to ballot-box stuffing, voter intimidation and other types of fraud, or even counting errors or the rare loss of ballots from just one polling station. The electoral system makes this sort of rigging extremely difficult, and is highly fault-tolerant against slip-ups whether they are deliberate or accidental. It is also unlikely to produce a tie, in which case the Constitution says the election is decided by a vote in the House of Representatives. This has happened twice, the last time being nearly 200 years ago. In every election since the electoral college has delivered a very clear decision.

Another solution is to eliminate the additional two electoral votes per state. This sounds especially appealing when you realise that the whole reason we even do this relates indirectly to slavery being legal early in our history. I’m not going to go into the specifics of this, here. It’s sufficient to say that taking away those two electors from each state just puts us back to the first scenario where states with larger populations have the electoral edge. (Click here for a more detailed explanation of the link between slavery and the electoral college.)

Vote-splitting — allocating a states electoral votes in proportion to the popular vote — is yet another popular idea. Where there are only two candidates this amounts to nothing more than the system I described at the beginning of the example. Furthermore, suppose a state had only two electoral votes. How would you split these between two candidates when one of them had a significant majority in the popular vote? If there were more candidates, there would still be two major ones, leaving the other, minor candidates to function as little more than spoilers. It doesn’t really solve the problem; it merely “kicks the can” down the road a bit further. (You can begin to see why the Framers left this up to the states.)

You Can’t Fix “Stupid” … or “Lazy”

I believe that the real problem isn’t the electoral college; it is the electorate — the voting public — themselves. Any system that puts such important decisions to a vote as we do REQUIRES participation in that system for it to work properly. That means that eligible voters MUST VOTE, at the very least. When too few show up, the system becomes unstable, “wobbly” and decisions like electing a new president become about as random as flipping a coin. The electoral result will still be quite definite, but it is just as likely to disagree with the popular vote as it is to agree with it.

The electoral college is designed to ensure a decisive victory one way or the other. In fact, it quite purposely punishes poor voter turn-out by often handing the election to the least popular candidate. And, for those who say, “But I did vote! For a third-party candidate.”, I would answer that the electoral college also punishes poor understanding and willful ignorance. To vote in the general election you must understand or at least accept that, like it or not, there are two main candidates and only one of them will win. Voting for a third party candidate because you think you shouldn’t have to choose between the “lesser of two evils” will almost certainly result in your vote helping to elect the greater of the two.

Summing it Up

This example is a simplified version of precisely what happened in this year’s election, as well as 2000’s and 1960’s. Instead of just six states, we have 50 (plus DC) and there are far more combinations of state populations and electoral vote tallies. But, the underlying mathematics is the same. You only need to know how to add numbers and compare them to see which is larger. It is tempting to say that anyone who can’t understand such basic arithmetic probably shouldn’t be voting. It is much more accurate to say that those who don’t vote can’t count.

This is a fun little puzzle inspired by the movie Babette’s Feast and my solution provided me with an opportunity to learn how to use the MathTex plugin for WordPress to render mathematical expressions.

The Problem:

For her feast, Babette invited many people to be seated around a round table. She prepared a table plan but all the guests arrived and took a seat so that everyone was sitting in front of somebody else’s place. Is it possible to turn the table so that at least 2 guests are sitting in the right place?

The Solution:

The short answer is, Yes, it is possible. Another way to phrase this is to ask, Does there exist an arrangement of guests around the table such that prior to rotating the table, no guest is found at his or her assigned seat, and following a rotation of the table (guests remaining where they are) at least 2 guests are at their assigned seat? Consider two specific cases. (Note that the number of guests is always the same as the number of assigned seats. For simplicity, we’ll assume the table is round, and we’ll also assume that both the guests and the seating are equally distributed around the table so the space between any two seats is the same for all seats around the table.)

Case 1: Just two guests, each initially at each other’s assigned place, π radians apart. Rotate the table through π radians and both guests are now seated at their assigned seats. (Somewhat trivial, and yet it looks like it might be a nice base case for a proof by induction.)

Case 2: More than two guests, each seated one place to the left of their assigned seat. Rotate the table clockwise one place and every guest is now seated at their assigned seat.

But, the problem is harder than that, isn’t it? We want to know if, for ANY given seating arrangement and distribution of guests where no guest is at his or her assigned seat, if it is possible to rotate the table to where at least 2 guests are now at their assigned place.

Let’s define the distance between a guest and his/her place be the minimum number of places to the left or to the right the table would need to rotate for that guest to find themselves in front of their assigned place. Note that is never more than where n is the number of guests.

If every guest were maximally distant from their place, the sum of these distances would be bounded above by or . The actual sum of the distances is given by

Rearranging this a bit gives us

Notice two things: First, this is only defined if there is at least one misalignment. Since we’re not interested in the fully-aligned case this isn’t a problem. The second, and more important thing to notice is that the minimum actual distance will never be less than 2. This makes intuitive sense if you look at case 1, above. But, consider yet another case where n > 2 and all of the guests are in their proper seats. The minimum misalignment possible is achieved by picking any two guests seated next to each other and having them swap seats. The distance between all other guests and their respective places will be zero, but for each of these two guests it will be 1. 2 x 1 = 2, i.e. our lower bound. Since the left-hand side is a constant, this holds for all n > 1.

Keeping this same arrangement in mind, observe that no matter how many times we rotate the table, in either direction, we cannot return these two to their original (i.e. correct) places. We can misalign all of the other guests by rotating just one seat to the left or to the right, leaving at least one of the two misalligned seats still misaligned. To put this another way, we have constructed two subsets of seats – the misaligned subset, and its complement, the aligned subset. Moreover, there can never be just one misaligned pair; there must always be two.

Now, consider the two sequences {g} and {s} which represent arbitrary but otherwise fixed orderings of our guests and their seats. Suppose the first element of {g}, aligns with the first element of {s}, . If we examine the rest of {g} vs {s} we’ll either find a match … or we won’t. If we find another match, we have our two guests seated at their assigned places and we can start the first round of aperitifs.

But, if the first elements do not match, the drinks must wait. We rotate {s} so that becomes , for i in [1,n], moving to . We apply multiple rotations until an aligns with , and look for a second matching pair. Again, if we find a second matching set, we’re done. Drinks are on. If there isn’t a match (put the decanter down, colonel) we still have more work to do. Rotate {s} again until aligns with and look again. But, notice that our search space has shrunk by 1. We can continue doing this all the way down until we are looking at matching an (after some number of rotations) and a that must match . Why must it? Recall that even in the most minimal misalignment of guests vs seats, there will be at least TWO mismatches. Consequently, by rotating through all of the matches, then mismatching them by rotating, we are isolating those mismatches. And these aren’t just any mismatches. These are mismatches that are NOT swaps. In fact, they are in the complement of the set of mismatches resulting from swaps, making them mismatches by rotation. Since all we have done is rotate the elements within {g} and {s}, and not change their order, we have accomplished what we set out to do: we have rotated the seats (i.e. places), keeping the guests stationary, until at least two of the guests find themselves at their assigned place.