Quantum Computing #3: Measurement + Review

Previously:

Introduction
Single Qubit Gates
Multiple Qubit Gates

Why One?

When we looked at the state of a single qubit, ψ = α0 + β1, we noted that this vector had to be of unit length, a stipulation encoded in the normalization condition |α|² + |β|² = 1. Similarly when we extended to a 2 qubit system, ψ = α00 + β01 + γ10 + δ11, we maintained the analogous constraint |α|² + |β|² + |γ|² + |δ|² = 1. This was accomplished by only ever applying so-called unitary (magnitude-preserving) matrix operations to the current state.

The reason for this has to do with the method of getting results out of a quantum computer, which is done by the process of measurement. The outcome of a given measurement operation can be any one of the system's basis states. that is, it will be either 0 or 1 for a single qubit system; 00, 01, 10 or 11 for a 2-qubit system; and so on. Which of the basis states actually gets detected depends upon various probabilities, and in fact these probabilities are just |α|², |β|², etc.

So to clarify, when we perform an operation of measurement in the computational basis on an n-qubit system, we are effectively forcing the state vector to settle into one of its 2ⁿ basis states. Taking the 2-qubit case as an example, the result of the measurement will be either

00 with probability |α|²,
01 with probability |β|²,
10 with probability |γ|², or
11 with probability |δ|².

Since these are the only possible outcomes, it's easy to see why the sums of the squares of the coefficients α, β, γ and δ must be unity - after all, there's a 100% probability the outcome will be one of these states!

Destructive Read

The measurement operation irrevocably destroys the previously existing superposition of states, leaving only the single basis state that is the result of the measurement. This means that the original state can never be directly observed. All that we can ever know about it comes from the results of destructive read operations.

For example, suppose we prepare a qubit in the 0 state, then immediately make a measurement. What will the outcome be? Well, the qubit state is ψ = 0 = α0 + β1, where α = 1 and β = 0. Measurement will deliver either the state 0 with probability |α|² = 1 (100% certainty), or else the state 1 with probability |β|² = 0 (0% impossibility). So far, so perfectly common sensible...

Now, suppose we pass the qubit through a Hadamard gate before making the measurement. The diagram below shows this new process:


The output of the H gate prior to measurement is ψ = α0 + β1, where α = β = 1/√2; so we have |α|² = |β|² = ½. In other words, the measurement is equally likely to deliver either 0 or 1; the probability of each is 50%. But regardless of which outcome is observed, the state of the qubit after the measurement is just that observed basis state; the original superposition of equal quantities 0 and 1 has been obliterated by the measurement operation.

Review

More than one reader still finds too much unfamiliar notation in my little introductory series, so here's a quick redux of the story so far, without all the matrices and Greek letters...

Qubits without Greek

A single qubit can be represented as an ordered pair of numbers (a, b), where |a|² + |b|² = 1. In this scheme, the pair (1, 0) represents the classical logical 0, while (0, 1) represents classical 1:

(1, 0) = 0
(0, 1) = 1

Similarly, an entangled pair of qubits can be represented as an ordered sequence (a, b, c, d), where |a|² + |b|² + |c|² + |d|² = 1, and the four particular values (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) stand respectively for the classical states 00, 01, 10 and 11:

(1, 0, 0, 0) = 00
(0, 1, 0, 0) = 01
(0, 0, 1, 0) = 10
(0, 0, 0, 1) = 11

An entangled triplet is represented as a sequence of eight amplitudes (a, b, c, d, e, f, g, h), where |a|² + |b|² + |c|² + |d|² + |e|² + |f|² + |g|² + |h|² = 1, and the following correspondence holds between basis and classical states:

(1, 0, 0, 0, 0, 0, 0, 0) = 000
(0, 1, 0, 0, 0, 0, 0, 0) = 001
(0, 0, 1, 0, 0, 0, 0, 0) = 010
(0, 0, 0, 1, 0, 0, 0, 0) = 011
(0, 0, 0, 0, 1, 0, 0, 0) = 100
(0, 0, 0, 0, 0, 1, 0, 0) = 101
(0, 0, 0, 0, 0, 0, 1, 0) = 110
(0, 0, 0, 0, 0, 0, 0, 1) = 111

When our quantum computers are big enough to contain n entangled qubits, there will be 2ⁿ coefficients or "amplitudes" a, b, c, ..., and still the sum of all their squares will be 1.

Quantum Gates without Matrices

Like classical logic gates, quantum gates are defined by the operation they perform upon their inputs. In the case of a single qubit gate, we could say the input state (a, b) results in the output (a', b'):

(a, b) → (a', b'),

where of course |a'|² + |b'|² = 1. The single-qubit gates we looked at in part 1 were: firstly the quantum wire I, which transmits the input qubit unaltered:

(a, b) → (a, b)

secondly the quantum inverter or NOT gate X, which swaps the two amplitudes of its single-qubit input, and so in particular, converts classical 0 to 1 and vice-versa:

(a, b) → (b. a)

(1, 0) → (0, 1) = 0 → 1
(0, 1) → (1, 0) = 1 → 0

and lastly, for a bit of quantum exclusivity, the Hadamard gate H, which can combine pure basis states:

(a, b) → ((a+b)/√2, (a-b)/√2)

You might find this last operation written without the √2 scale factors, particularly in multi-step quantum computations, when it is common to roll up such adjustments into a single normalization following the final step of the calculation:

(a, b) → (a+b, a-b)

The only multiple-qubit gate we've seen so far is the controlled-NOT or cNOT gate, which swaps the last two amplitudes of its entangled input qubit pair:

(a, b, c, d) → (a, b, d, c)

By explicitly tracing through the details of the four transitions, we found that this twist corresponded to an inversion of the second qubit, if and only if the first qubit was 1:

(1, 0, 0, 0) → (1, 0, 0, 0) = 00 → 00;
(0, 1, 0, 0) → (0, 1, 0, 0) = 01 → 01;
(0, 0, 1, 0) → (0, 0, 0, 1) = 10 → 11;
(0, 0, 0, 1) → (0, 0, 1, 0) = 11 → 10.

Measurement

Finally, in the first half of this article, we have just covered the question of getting results out of the qubit complex. When you perform a measurement in the computational basis, the single qubit (a, b) will deliver a result of either (1, 0) = 0, with probability |a|², or else (0, 1) = 1, with probability |b|². The qubit will also adopt that measured state, from the point of the measurement onwards; having collapsed into probabilities, there now remains no trace of the original state amplitudes (a, b).

To take a numerical example, the (unknowable) initial state of the qubit might be (a, b) = (+0.8, -0.6). Now suppose a measurement is performed on this qubit. The outcome will be either 0, with a probability of |a|² = 0.8² = 64%, or else 1, with a probability of |b|² = 0.6² = 36%. Notice that the two outcomes have probabilities adding up to 100%, and that between them, they exhaust all the possibilities.

A similar measurement upon a qubit pair in the state (a, b, c, d) will yield a result of (1, 0, 0, 0), i.e. 00, with probability |a|²; alternatively, a result of (0, 1, 0, 0) = 01, with probability |b|²; and so on.

Next time: Superdense Coding.

China Commands And Controls

Over 90% of C&C Centres in Beijing

Last March security firm RSA revealed one of the most spectacular data breaches in history. Not because of the methods used, which were a combo of a Trojan and some fairly elementary social engineering (though perhaps understandably, RSA felt it necessary to characterise the breach as an extremely sophisticated cyber attack). Neither because of the quantity of data compromised in that one attack. But because of the sensitivity of the data, which compromised in turn the SecurID two-factor authentication products, and hence the crown jewels, of many other corporations and organisations.

Back then, security experts claimed that "dozens of other multinational companies" were simultaneously infiltrated in much the same way. In fact the truth now emerges to have been closer to 760 or more organizations, including almost 20% of Fortune 100 companies, who had their networks hit by the same resources as were used against RSA, in a series of attacks which actually began last November. Brian Krebs has the full list here.

But even more startling is the following chart, which shows the geographic distribution of the command and control networks used to coordinate these attacks:

299 of the 329 Command & Control centres are in or around Beijing.

Avira Attacks Self

It's like CA eTrust all over again

Always a bit of a guilty laugh whenever this happens to some poor unsuspecting antivirus vendor. After Wednesday's signature update, Avira's freebie anti-virus offering started marking certain components of its own code as "potentially malign".

Stefan Berka of Avira Operations broke the news thusly on their own support forum: Hello, We have had an false positive for the Avira file AESCRIPT.DLL which was detected as "TR/Spy.463227". Their statistics show around 4,000 false positive samples received on Oct 26, before the fixed Virus Definition File was deployed.

False positives in application files or Windows components are actually quite common, particularly in free offerings like this one, but the last time such an "auto-immune" false detection is known to have occurred was over two years ago, when the CA eTrust antivirus went completely mad, renaming and quarantining parts of itself, together with various bits of MS Visual Studio, Incredibuild, and others. Users at that time were advised to block the update, as well as to consider temporarily disabling on-access scanning. And that was only one month after its previous attack on them pesky Windows system files.

Quantum Computing #2: Multiple Qubit Gates

Previously:

Introduction
Single Qubit Gates.

Entanglement

Last time we saw that a single qubit can be in either basis state, 0 or 1, or any normalized superposition of the two:

ψ = α0 + β1, where |α|² + |β|² = 1.

When we come to analyse systems of two or more qubits, it's important to realise that we don't just replicate the above, once per additional qubit, as we would in classical logic. This is because qubit states can be entangled. They have to be treated as a whole: as the overall state of the qubit set. Therefore, to take the next simplest example, a two-qubit system can be in any of the four basis states, 00, 01, 10 or 11, as well as any normalized superposition of these four:

ψ = α00 + β01 + γ10 + δ11, where |α|² + |β|² + |γ|² + |δ|² = 1.

As before, we can introduce an arbitrary set of orthogonal column vectors to represent each of these four basis states,


which gives us this representation of the multi-qubit state as a column vector:

and in general, an n-qubit system will have 2ⁿ pairwise independent (orthogonal) states in its computational basis, and hence 2ⁿ components in its state column vector.

The Controlled-NOT Gate

Recall what single-qubit gates such as X and H looked like: 2x2 unitary matrices operating on unit state column vectors. Similarly, n-qubit gates are represented by unitary 2ⁿx2ⁿ matrices. Our next example is termed the Controlled-NOT gate, or cNOT (feel free to invent your own pronunciation). This has two inputs and two outputs. The first input is passed through unchanged to the corresponding output. When this first input is 0, the second input is also passed through unchanged to its corresponding output. But when the first input is 1, the second input gets inverted as through an X gate. Here is the matrix representation of cNOT, and its operation upon a general 2-qubit state column vector:

To see exactly how this matrix represents a cNOT operation on two qubits, we consider its effect upon each of the four basis states in turn:

By checking each of these four cases in turn, we can confirm that the gate operates as advertised in the description above. Finally for the sake of completeness, and courtesy of Wikipedia, here is the circuit diagram symbol of a cNOT gate. The top quantum wire represents the "control" qubit, which is transmitted unaltered, while the bottom path represents the "controlled", i.e. conditionally inverted, qubit.


Miscellany

That's the meat of the present article in the series. I'll finish with a couple of general remarks on what we've seen so far.

There's actually an entire family of controlled gates similar to cNOT, differing only in the particular single-qubit operation that's applied to the controlled qubit when the control is 1. Their matrices are easily obtained by substituting the single-qubit operation's 2x2 sub matrix in the bottom right quadrant of cNOT.

All quantum gates have square matrix representations, since they all have the same number of outputs as inputs. That's because quantum computations have to be reversible. It's easy to show that gates like the classical AND, OR etc. can't be made reversible, as there's less information in their output (one bit) than in their inputs (two or more bits). This also implies that those classical gates necessarily dissipate energy during their operation.

Next time: Measurement; also, a Review of the story so far, devoid of matrices & Greek letters!

Electro '08

Top 5 Electro of 2008?

This week French shoegazy dreampop act M83 released their sixth album, the two disc Hurry Up We're Dreaming, prompting the impeccable Dan Cairns (Sunday Times) to compare it to their previous, Saturdays=Youth, "the twin peak - with Cut Copy's In Ghost Colours - of 2008 electro". The comparison seems to be made a little unfavourably, though exactly how much so would have been easier to gauge had not the ST sadly, recently, discontinued its out-of-five star ratings.

Fussy genre definitions thus loosened, the comparison elicits the above question. Chiefly because Dan is always right. He has technical and theoretical musical knowledge, setting him apart from most so-called music critics. He knows, and will show you on a stave, exactly why the songwriting of Charlotte Hatherley must be cherished. Two weeks ago, he declared Lana Del Rey's Video Games the song of the year, with disregard to the currents of hype and other irrelevancies engulfing that artist. Declared it as scientific fact; Dan does not equivocate, nor trade mere opinion.

So yeah, he's right too about the eminence of both acts in the twin peak quote. But which of their songs are the true, 80s-retro royalty of 2008? And what other acts and tracks deserve inclusion beside these?

I'll start...

Oddly enough, M83 were not named after the south/east section of Glasgow's M8 junction 25, between the Clyde Tunnel Expressway and the South-Link Motorway. In fact no UK road has ever received that designation, which only ever appeared on that one Corporation / Fairclough gantry and local route sign drawing. So they chose instead to be named after the Southern Pinwheel Galaxy, a barred spiral in Hydra.

They released a prolific four singles in 2008, all from the haunting Saturdays=Youth. The second of the four, Graveyard Girl, is naturally the most haunted - even without its haunty spoken section:

I'm 15 years old
and I feel it's already too late to live
don't you?

Now let's get the second half of the twin peak quickly out of the way: Cut Copy. Nobody, not even Jeff Lynne himself, ever channeled ELO better than the Aussies' So Haunted. However, my vote goes to track one, for the Melbourne electro outfit's funky 80s retrocapture tech, first displayed here at 1:17:



The production work lavished on MGMT's fairly ordinary ditties by Mercury Rev / Flaming Lips producer Dave Friddman elevated Oracular Spectacular to electro royalty, and 2008 saw a total of four singles released from it, from Time To Pretend through Kids. I won't pretend to choose between those two.





Ladytron continued to innovate with their fourth album Velocifero in 2008, and particularly with a change of direction in their first single Ghosts. This might have given them their worst UK chart performance of the millennium to date, but the more typically daytronic Runaway laughingly made up for that with a breakthrough at #30 in the US dance chart:



Finally a confession: this isn't actually my top 5 electro from 2008. A well-thumbed TSM Radio review from May 2008 fondly recalls Epic New Song by the now tragically defunct Futuristic Retro Champions. Now, I honestly don't know whether this is my favourite FRC, since I once tried in vain to grade them all for a playlist, ending up with a total of twelve songs scoring 10/10. So my sixth and final, thank you, goodnight and safe home selection, is a sampling (the full collection Love And Lemonade is available at iTunes) of the most emotronic happy hardcore ever committed to disc ... in or around 2008.

Epic New Song - Futuristic Retro Champions by everythingflows

Jenna - Futuristic Retro Champions by everythingflows

Told Ya - Futuristic Retro Champions by everythingflows

Your mileage may vary. Hey, I'm no Dan Cairns.

Image credits: M83 road sign, Messier 83, all via Wikipedia.

Quantum Computing #1: Single Qubit Gates

Previously:

Introduction

Mathematics? What Mathematics?

Recent mention of Mike Nielsen's Quantum Computation videos sparked a flurry of interest among friends and colleagues, mostly tempered by wariness about the mathematics involved. That's a pity, because there's actually very little mathematics needed to make a start on this stuff. Complex numbers, for example, are not strictly essential for an introduction to the subject. And even when they become so, well after all, they are just pairs of normal numbers, with a special rule for multiplication. Similarly, matrices are nothing more than a shorthand way of multiplying ordinary numbers pairwise, two by two, and then adding up the results.

Still it can be a sub-optimal experience to jump into Wikipedia's Quantum gate page, finding yourself immediately surrounded by not only these, but also the curious ket notation. Well, let's at least see if we can get started without that!

This is the first in a series of articles on quantum computation, to be published over the next several Sundays, loosely following the content of Prof. Nielsen's videos. It describes, in a thoroughly simplified style, a couple of single-qubit gates. Future articles will apply the same stripped-down approach to multiple qubit gates, and then measurement, and in surprisingly short order, superdense coding and quantum teleportation.

Another unusual aspect of these articles, also owed to Prof. Nielsen, is the complete lack of any reference to physical implementations of quantum gates and circuits. This is just how classical Boolean logic (or the propositional calculus) developed historically, many years before physical AND gates were realised in switches, valves, water sluices, dominoes or marbles. We simply describe a two-value quantum computational algebra, taking it on trust that there's no shortage of potentially available physical realisations.

The Computational Basis

Like a classical, logical bit, the quantum bit or qubit has two computational basis states; 0 and 1. Some writers use instead ↑ and ↓ to represent the basis states. Personally I'd have preferred to use something like T and F, but hey. Whatever symbols are used, they're usually embedded in the forementioned ket marks, like these:

but for purely typographical reasons I'll be omitting those, at least to start with, and using instead just the bold 0 and 1.

For the purposes of the matrix transformations which follow, the basis states can conveniently be represented by any two orthogonal unit column vectors. Note that the unfortunately named 0 is not the zero vector; 0 is just a label for the ordinary, basis state vector we've chosen to represent "logical zero". For example, the labels 0 and 1 might represent unit steps in some arbitrary x- and y-directions, respectively:


The qubit's actual state ψ can also be any linear combination (or superposition) of these basis states,


where |α|² + |β|² = 1.

Quantum Gates

Quantum computing has its own "gates", by analogy with the classical AND, OR, NOT etc. These can be represented by square matrices. For example, a single-qubit gate might be represented by a 2x2 unitary matrix M.

Wait, what? Unitary? - Well, a gate matrix multiplying any given quantum state column vector yields a new state, and this new state must also satisfy the above normalization condition, |α|² + |β|² = 1. Unitary matrices are just those which preserve this criterion. In other words, they preserve the unit length of the state vector ψ.

The simplest quantum gate is the single-qubit "wire", which - pay careful attention now - looks like this:

and just transmits the state vector unaltered. The matrix representation of this is the 2x2 Identity matrix, I.


The NOT Gate

For historical reasons, the quantum NOT gate is also known as the Pauli-X gate, and appears in both circuit diagrams and matrix representations as the letter X. Here's its symbol for use in quantum circuits:

This gate "inverts" its input, in the sense that given an input of 0, its output will be 1; and conversely, given an input of 1, its output will be 0. As for those peculiar superposition states, it seems reasonable that an arbitrary input state ψ containing a certain quantity α of the 0 basis vector, together with a corresponding quantity β of the 1 basis vector, should upon passing through a NOT gate, have those quantities reversed. And that's just what this X does:

Like the classical logical inverter, the quantum X gate is its own inverse. In terms of linear algebra it's trivial to show, by explicit matrix multiplication, that XX = I:

The quantum circuit diagram below is therefore equivalent to a single wire.


The Hadamard Gate

Our first truly quantum gate, without a classical analogue, is the Hadamard gate H. Given an input of 0, its output is the sum of the 0 and 1 basis states (normalized, of course). Similarly, given an input of 1, its output is the normalized difference between the two basis states. It's like this:

The √2 is the normalization adjustment needed to give the output vector unit length. "Noise" like this is often omitted from practical quantum computations, it being universally acknowledged that the state vector always requires such normalization; but I'll retain it, to avoid confusion.

The Hadamard gate is also its own inverse. In terms of linear algebra it's trivial to show, by explicit matrix multiplication, that HH = I:


and hence that the series circuit of two Hadamard gates, just like the case of two inverters, is also equivalent to a single quantum wire.

Next time: Multiple Qubit Gates.

The Dangerous Mod

Popup Worry

Kaspersky continues to perform as one of the best available Internet security packages, and although everyone is only ever one slip away from a major breach and a catastrophic loss of reputation, I would not hesitate to recommend it. Maybe that's why I've given this little popup notification a bit more attention than it warrants at first sight.

A look in the usual forum or three reveals that people have indeed found messages like this one quite confusing. For one thing, they are unforgivably ambiguous. Is it the application, or the modification, that is being flagged as "potentially dangerous"? And quite separately, which one is it that has no digital signature - the original app, or the process (installer) trying to update it?

Then there's the question of relevancy when it comes to "98% of users trust this application". Do they trust the modified or unmodified version? And why exactly do they trust it? You don't have to be particularly security savvy to know: the mere fact that "more than a million" users have run a program, doesn't prove it's not malware. Aren't those users being a little bit cavalier, at this time of apparently ubiquitous fake certificates?

Of course, clicking "Help" does nothing to improve matters, unless you count as progress, advice on how to prevent these pesky warnings from appearing at all. The so-called "Help" link just takes you to a description of popup warning management options within the security app itself, completely oblivious to the context of your present dilemma!

Finally, I have to grumble about the available options. None of these is entirely satisfactory. Yes, I trust - as we have just been told - obviously risks running a "potentially dangerous modification of the application". Yet how is a typical user supposed to evaluate the Restrict option? Why on earth would you ever consider allowing "dangerous operations" in the first place?

As for the seemingly safe Block option: nothing terrifies me more than the prospect of trying to update my wife's iPad2 to iOS5, as I am destined soon to do, then being blocked halfway through an elaborate backup / restore operation because the necessary instructions are stuck in a blocked QuickTime Task. Where is the "Ask me later, when it actually tries to do something" option? Remember, almost everyone now has this kind of update configured to run automatically in the background. I probably won't want to have to deal with this warning as soon as it pops up. Yet it cannot be dismissed without making an apparently irrevocable decision about the fate of a potentially critical app.

Nor can it be ignored; it's a stay-on-top window.

Calm Down, Dear

Now, it goes without saying (to security experts like you and me :-) that the correct option is to click the inconspicuous little information icon beside the application name, and verify as many details as possible, sans signature. In this case, the app name, path, vendor, product version and create / modified dates check out, while I can see that it's the original app that had no sig. Hey, it's been running that way since July! Only now is the warning disambiguated: it's about the modification of an unsigned file.

Here, both the original file and the agency performing the modification are trusted. So I choose Yes, I trust and get on my way.

This rant is all about UI design and user guidance. Kaspersky, you might be as I contend, the best in the personal computing security business; but you sometimes make the mistake of assuming you're communicating with colleagues. Often instead, you need to explain as you would a child.

Quantum Computing for the Determined

Moving Pictures

Nobody seems willing to predict when quantum computing will take off. Some are even beginning to question whether it will ever do so. Meanwhile, optimists patiently await that crucial breakthrough, the discovery of the perfect physical realisation of the qubit. There's no shortage of candidates. The Nitrogen Vacancy (NV) centre in diamond is one. NVs are the crystal lattice imperfections in pink diamonds that give them their hue. Then again, a lot of progress has recently been made involving trapped ion systems.

The optimists wait - impatiently, on second thoughts! - for one of these, or for some other exotic virtual particle inhabiting some material (or as yet unknown metamaterial), that will finally and abruptly realise the qubit as coherent, entangled and scalable.

As they wait, they polish their grasp of linear algebra, matrices, the various fundamental and second-order quantum "gates" that have been conceived, and the circuits made possible by these. Rehearse the limitations imposed by their fragility and inscrutability. Marvel at the astonishing algorithms that have been developed in qubit theory, while worrying about their scant number and opaque discoverability.

Almost to a man or woman, they have found and honed their new algebraic skills using The Book: Quantum Computation and Quantum Information, by Michael A. Nielsen (University of Queensland) and Isaac L. Chuang (IBM / Stanford University). Or Mike and Ike, as this revered tome is universally known. A literally pioneering work, it was the first of its kind, and is still today the standard to which all else is inevitably compared (my earlier review is here). In fact it's the most highly quoted physics publication of the last 25 years, and one of the ten most highly quoted physics books of all time (source: Google Scholar, December 2007).

In support of its tenth anniversary edition, Professor Nielsen has released a set of 22 short video lectures on his blog. They're a great introduction to the subject. However, he has stopped just short of completing the course, due to intervening work commitments. He has promised to complete it if there's enough interest in the videos produced so far. Here's the first one:

You know what you must do!

Next time: Single Qubit Gates.