Taking into account quantum encryption (part 2)

This is the second part in an article on quantum cryptography and communications, and will cover the usefulness of quantum computing and physical realizations of quantum computing, and tie it all together for quantum cryptography and communications. There will also be some resources listed if you’re interested in learning more about quantum computing. This article continues from part 1.

Physical realization (circuit-based)

First, let’s consider whether or not it is possible to actually build a quantum computer. The answer is yes. In fact, there are many ways to build a quantum computer, though all of them are rather difficult. There are several main realizations that we’ll look at: optical quantum computing, superconducting quantum computing, ion trap quantum computing, and nuclear magnetic resonance quantum computing (though this is not to say that these are all the methods — there are many others).

Optical quantum computing

Optical quantum computing represents qubits using photons. Yes, that’s right — you can compute using light. Optical components such as phaseshifters, beamsplitters, and mirrors correspond to various single qubit gates. A standard mirror, for example, provides a 180-degree phase shift, corresponding to the Pauli-Z (pronounced ‘zed’) gate.

One system uses just linear optical components like these, but an exponentially increasing number of them are required for each new gate, making it inefficient for computers large enough to be practical. Other systems use nonlinear media to entangle photons — for example, spontaneous parametric down conversion can be used, which sends laser light through certain crystals which can entangle one photon pair in every 10 to the 12 photons. This low rate of success also makes larger computers difficult.

Other systems, purely theoretical, use nonlinear Kerr media (materials which produce an electric field dependent on the intensity of the light that enters it), which rely on the AC Kerr effect, though this effect is too small to be used when only a single photon enters the Kerr media. The system that is most commonly built uses a Fabry-Perot cavity to act as the nonlinear media.

Ion trap quantum computing

Ion trap quantum computing uses ions to act as qubits. It manipulates their state using laser beams, and keeps the ions in place using magnetic fields (the ‘trap’ part of the system). The current downside to this realization is that it is incredibly difficult to construct a magnetic field that will create a 3-d structure of ions for more efficient interaction between qubits. Current systems use a 2-d setup of the ions.

A paper has recently been published proposing a quantum computer the size of a football field which uses this realization; whether or not it will be actually built remains to be seen. It sections the ions into “units” which can be used to solve chunks of the overall problem. The proposal is one of the first that provides a specific, actionable method to build a larger quantum computer, but it may not work as described; the paper is purely theoretical.

Superconducting quantum computing

Superconducting quantum computing has perhaps the best shot at becoming the best realization to use. It is much more scalable than the other systems, though one disadvantage is that dilution refrigerators must be used to cool the qubits to around 10 milli-kelvin to avoid thermal fluctuations which might mess with the state of the qubits. Google and University of California-Santa Barbara’s joint Martinis Lab, for example, uses this approach.

The qubits here are realized with superconducting circuits which include Josephson junctions. These qubits are then “hooked up” to other qubits using intermediate circuits, and this is done to apply gates requiring multiple qubits. Single qubit gates are produced by microwave pulses. Measurement is generally done with a microwave resonator, which is basically something that oscillates at a certain frequency.

A standing wave in a rectangular cavity resonator. Image credit/caption: Wikipedia

The qubit’s state then affects that frequency, so experimenters can see the difference and determine the qubit’s state.

Nuclear magnetic resonance quantum computing

In nuclear magnetic resonance (NMR) quantum computing, qubits are represented by the spin states of the nucleus in atoms. There are two types of NMR — liquid state (LSNMR) and solid state (SSNMR). In LSNMR, the qubits are represented by atoms in a liquid, versus atoms in a solid in SSNMR. SSNMR is considered easier to work with due to the fact that it can be taken to lower temperatures to prevent decoherence and it is easier to initialize, or “start”, the qubits in a certain state.

To apply gates, a strong magnetic field is generated, and then radio frequency pulses are applied to change the qubits’ states. This is why the system is called NMR quantum computing.

Errors, noise, and other difficulties

Now, along with all this, there are some other considerations when moving from theory to practice, independent from which realization you choose. Qubits do not stay ‘quantum’ forever. Eventually, they decohere, which happens more quickly the more they interact with their outside environment. This wish to isolate qubits from their environment must be balanced with the need for the qubits to be able to ‘couple’ with other qubits in multi-qubit gates. Thus, a solution must be a balancing act, aiming for the middle ground between the two problems.

Another problem is noise — changes in heat, some movement nearby, or other such things can cause changes in the state of qubits that wreck the whole calculation. Enter error correction. Error correction is used in classical computing as well, to (as the name aptly says) correct errors that come up in operation. There’s a quantum version too (called, unsurprisingly, quantum error correction), but it’s a little different, and that’s partly due to the no-cloning theorem.

The no-cloning theorem says that you cannot copy the state of a qubit. Cannot. Impossible. And, unfortunately, as far as we know, there’s no breaking physics (nor would we want to). This makes error correction kind of hard. The methods ingeniously contrived involve the use of other qubits that are used solely for error correction, due to some reasons we’ll not go into here.

This all is not to say that soon, instead of your laptop, you’ll be pulling out your ‘QuApple’ laptop anytime soon. You won’t check your email or watch videos on a quantum computer, but it will affect you.

Adiabatic and cluster based computation

We’ve so far been talking about circuit-based quantum computation — that is, using applied gates to change the state of the system. There are other types of quantum computing, however — among them, adiabatic and cluster-based.

Adiabatic quantum computing uses the concept of finding the lowest points of a system. Think of it as setting a ball on a hill. It will naturally roll to the lowest point in the system (the state). However, a problem arises — the ball might get stuck in a little dip at the top of the hill. (These small “local” dips are called “local minima” in mathematical parlance.)

To account for this, Google came up with a system that starts with a |0>-state (in our example, this would correspond to placing the ball on the flattest space you could imagine) and then slowly evolves it into the end state (in our case, the hill — you might imagine slowly raising a small hump in the middle, and over time that hump growing and growing into our full hill).

Adiabatic quantum computing is useful for optimization problems — trying to find the most efficient solution to the traveling salesman problem, for instance.

Cluster based quantum computing is a very interesting technique dependent on measurement changing the system. First, a bunch of qubits are entangled with each other in certain ways, and then measurements are performed in certain bases to change the state towards the wanted end state.

However, in my opinion, the most widely useful method is circuit-based quantum computing, so that’s what we’ll focus on.

Usefulness

You may be wondering (for good reason) how all this, aside from its interesting-ness and scientific value, is actually useful. Aside from the fact that it can efficiently simulate quantum systems, which is of extreme value to physicists, there are also multiple algorithms that have been discovered which are faster than current classical algorithms. We don’t know yet for sure whether or not these are faster than the best possible classical algorithm, but we think they are.

Algorithms

One of these algorithms is Grover’s algorithm, which is a more efficient search algorithm. Arguably the most famous, though, is Shor’s algorithm, which was discovered by Dr. Peter Shor at the Massachusetts Institute of Technology (MIT). The algorithm can find the prime factorization of numbers very efficiently. This discovery sparked a wave of interest in quantum computing, which is a relatively young field.

The reason Shor’s algorithm is so important is because most of our encryption systems today are based on the inability of classical algorithms to efficiently find the prime factorization of numbers. This method is called RSA encryption. Because Shor’s algorithm basically renders this method obsolete, a whole new subfield in communications and cryptography has been created for ‘post-quantum’ study.

While currently the largest quantum computers are only 15 or so qubits (excluding the company D-Wave, around which there swirls a large controversy about whether or not its qubits are actually quantum bits), Google’s Martinis Lab is planning on constructing a 50 qubit computer by the end of the year, and quantum computers are getting better and better incredibly fast. Shor’s algorithm has already been demonstrated on smaller numbers, such as 15. Researchers, therefore, are working to develop better forms of encryption and communication that are safe from attacks from quantum computers.

Quantum Cryptography

The most well-known application of quantum cryptography, and the one we’ll discuss here, is quantum key distribution (QKD). Say we have two people, Alice and Bob, talking, and a third person, Eve, attempting to eavesdrop (sorry, couldn’t resist that pun). QKD basically means that when Eve tries to learn about the key Alice and Bob are using, Alice and Bob will notice that the key has failed, so Eve gains no information.

What is interesting about this method is that it isn’t dependent on the weakness of computers, like RSA encryption, but on fundamental principles of physics, meaning that quantum computers can’t break QKD, and as far as we know, nothing can.

It should be noted that quantum cryptography is not to be confused with post-quantum cryptography. The former uses quantum mechanical principles to encrypt things (i.e., you need a quantum computer to encrypt your information), and the latter refers to algorithms requiring only a classical computer meant to be secure against a quantum computer. The current major post-quantum algorithms actually could be beaten by a large enough quantum computer, though researchers are working on this.

What I haven’t said (but will summarize)

There’s some points I’ve neglected to mention in these two articles, for the sake of clarity, space, and irrelevance to the major points covered. A few of these are quickly (if not quickly enough, feel free to skim or skip) summarized here.

Unitary matrices

First, for a gate to be allowable, the matrix representing it must be unitary. A matrix is unitary if the hermitian of the matrix U times the original matrix equals I, the identity matrix. The hermitian operation (represented by a small superscript dagger) first takes the complex conjugate of the matrix, that is, changing the signs on any component in the matrix with a complex number in it (i.e., 3 + 2i would become 3-2i; note the sign on the real value in front, in this case 3, is not changed) and then takes the transpose of the conjugated matrix.

To take the transpose, one makes the first column into the first row, the second column into the second row, and so on, by “swinging” them up (the order of the components of the column is not changed). The identity matrix can be recognized for the 1’s going down the diagonal of the matrix (in a 2x2 matrix, the top left and bottom right spots are filled with 1’s) with the rest of the entries being 0. When any matrix is multiplied by the identity, the matrix stays the same, much like when you multiply a real number n by the multiplicative identity, 1, the result is n (1 times any number is the same).

Also related to this is that the length of the vector representing the state of the qubit(s) must have a length (or ‘norm’ in linear algebra speak) of 1. To check the length of the vector (though if you are using unitary matrices, the length will not be changed, so there’s no need to manually check), add all the components and find the square root of the sum.

The basic reason this must be true is that the operations must be reversible, that is, fulfill time symmetry. An astute reader will notice that measurement, in fact, does not fulfill this requirement; more on that momentarily.

(Some) other linear algebra omissions

First, there are many aspects of linear algebra not covered even here in this section, but I’ll try to hit some highlights. Matrix multiplication is not commutative; that is, a matrix A times a matrix B is not the same as the same matrix B times the same matrix A. The second matrix ‘operates on’ the first.

Some things to look up for the interested reader — solving systems of linear equations can be done quite easily with matrices; this involves (depending on the system; there are multiple techniques) Gaussian elimination, that is, getting the matrix into row echelon or reduced row echelon form, finding the inverse of a matrix, and so forth.

Determinants are an important aspect of matrices not covered; one can determine if there is an inverse of a matrix by checking the determinant. Eigenvalues and eigenvectors are very important in quantum mechanics and linear algebra. If you wish to learn more, there are some resources listed down below.

A whole lot of computer science

For example (there’s much not touched on here; computer science plays a huge role in quantum computing), a central problem is quantum supremacy, which is (to summarize) whether or not quantum computers are actually faster/more efficient than classical computers. Part of this gets into complexity classes — for example, we have algorithms for quantum computers that are more efficient than those for classical computers, but we don’t know whether that’s just because we haven’t found those better algorithms yet, or because they don’t exist.

Computer scientists have come up with a categorization for problems, called complexity classes. The three I’ll talk about here are P, NP, and BQP. P is the set of all problems solvable and checkable in polynomial time, NP is the set of all problems checkable in polynomial time, and BQP is the set of all problems solvable and checkable by quantum computers in polynomial time.

Phew. What I mean by this is if I have a problem, and I can solve it decently efficiently (I’m not going into polynomial time and what that means here) and check if the solution is correct decently efficiently, then the problem is in P (we’re talking about a classical computer here). If the problem isn’t easily solved, but solutions are easily checked, it’s in NP. And if a problem can be solved and checked easily on a quantum computer, it’s in BQP.

Let’s look at two examples — normal multiplication and finding the prime factorization of numbers. Normal multiplication is in P — a computer can solve and check a multiplication problem very quickly. However, finding the prime factorization of numbers is in NP. That’s why it was chosen for the basis of RSA encryption, because it’s very hard to do. On the other hand, finding prime factorizations of numbers is also in BQP, and we know this because of Shor’s algorithm.

From this, you can see that P is at the very least a subset of NP, but what we don’t know is whether or not P = NP. If P = NP, that would mean that there would be an algorithm that could find prime factorizations of numbers on classical computers efficiently, as well as checking them.

Time symmetry, measurement

A commenter said the other day in one of Stack Exchange’s chatrooms that the measurement operation can actually be represented by a matrix. I’m still reading about it and messing with it so I understand it more, but I’ll just give a few comments here. The matrix is

You’ll note that it isn’t unitary, which makes sense, because the measurement operation isn’t reversible. If I gave you a qubit that was in the 1 state and told you it had been measured, and asked you to figure out its prior state, you’d have no idea, and that’s exactly what’s meant when we say it isn’t reversible. Classical mechanics is all reversible and deterministic, meaning that if you had a big enough, smart enough mind/computer, and accurate enough measurements, you could figure out the entire state of the world, past and future.

This has been semi-recently thrown into doubt even in classical mechanics by chaos theory (an oversimplification of which is to quote the oft-said phrase that when a butterfly flaps its wings in New York, there’s a storm in Tokyo), but it was absolutely crushed by quantum mechanics and measurement. There’s a whole lot of philosophical talk on what exactly measurement in quantum mechanics even means (if interested, look up the many-worlds interpretation, the Copenhagen interpretation, Bell’s theorem (which is very important in its own right, and I’d highly recommend reading about it), or just ‘interpretations of quantum mechanics’), but I won’t get into that here.

Basically, we thought everything was time symmetric, but it turns out that there are three symmetries the universe follows: C, P, and T, or charge, phase, and time. Everything follows these three symmetries together always, but not always individual symmetries — that is, something can be CPT symmetric without being T symmetric. My (crude) understanding is that the symmetries can sort of ‘cancel each other out’, so to speak. So there can be systems that aren’t time symmetric, and those are being studied with great interest. In spite of all this, the majority of gates used in quantum computing must be time symmetric as well as CPT symmetric.

This is, as I said, something I’m still reading about, so don’t take my word for law here — go read about it yourself!

Resources for the curious

Some resources, of varying difficulties, notated by B for beginner, I for intermediate, and A for advanced. QR will notate a “quick reference” — for quickly looking something up or asking questions. Beginner resources anyone should be able to go for, intermediate resources require a little bit of background, and advanced resources (many of them papers) will require quite a bit of blank stares and thought. All ratings are by my guesstimate, so you might very well disagree. Comments about more resources or ratings (or just plain old comments) are welcome.

Videos

• Quantum Computing for the Determined by Michael Nielsen. Link here. A set of videos on YouTube meant to get you up and going. Prerequisites — basic linear algebra and calculus. Difficulty: B if you have the prerequisites (mainly linear algebra, though a little calculus wouldn’t hurt).
• Essence of Linear Algebra by 3Blue1Brown. Link here. Amazing videos on linear algebra with great animations. If there was one thing you were to look at from this entire list, this would be it. A real gem. Difficulty: B
• RSA encryption videos on Khan Academy. Link here. A simple description of RSA encryption and how it works. Difficulty: B

Books

• Quantum Computation and Quantum Information by Nielsen and Chuang — literally the bible of quantum computing. Expensive, but if you can get ahold of a copy, it will cover almost everything you could want to know. Written by pioneers in the field. Difficulty: I-ish
• Quantum Computing Since Democritus by Scott Aaronson. Another one written by an expert in quantum computing. I have not read this one personally but have heard it’s good. Difficulty: B (as far as I’m aware)
• Elementary Linear Algebra by Larson and Edwards. I’ve used this one quite extensively myself, after picking it up at a used bookstore by luck. At the time, I was trying to figure out what a unitary matrix was. I figured it out in around a minute flipping through the book, so I bought it. Explains things succinctly and well, with some intuition to boot. Covers some linear programming as well. I’d recommend watching 3Blue1Brown’s videos first, though. Difficulty: B
• Introduction to Linear Algebra by Gilbert Strang. This is generally considered a classic linear algebra text. One of those rare math books that actually isn’t 100% definitions, theorems, and proofs. Difficulty: B

Websites

• Quantiki. Covers many topics, includes forum. QA
• Wikipedia. Covers many topics, though descriptions are not always ideal. QA
• Stack Exchange. Great for asking questions. Looking at past questions and answers is also quite informative. There are multiple sites within the stack exchange umbrella; relevant ones include Physics, Computer Science, Theoretical Computer Science (research-level version of Computer Science), Mathematics, and Math Overflow (research-level version of Mathematics). Also check out the chatrooms associated with each site, in particular the “hbar” — the Physics-associated chatroom (you need a certain amount of user points to participate). There is also a brand new Quantum Computing site, which I highly recommend. QA
• Shtetl Optimized is Scott Aaronson’s blog, which sometimes has posts on quantum computing. Difficulty: all levels, depending on post.

Papers

• Quantum Mechanical Computers, by Richard Feynman — the foundational paper in the field. Difficulty: I
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer by Peter Shor — the paper which introduced Shor’s algorithm. Difficulty: A
• A Fast Quantum Mechanical Algorithm for Database Search by Lov Grover. Paper which introduced Grover’s algorithm. Difficulty: A
• A Method for Obtaining Digital Signatures and Public-Key Cryptosystems by R.L. Rivest, A. Shamir, and L. Adleman — paper which introduced RSA encryption. Difficulty: I
• Quantum theory, the Church-Turing principle and the universal quantum computer by David Deutsch. Another of the foundational papers in the field. Difficulty: A
• Fast, Accurate State Measurement in Superconducting Qubits, a thesis by Daniel Sank, a physicist at Martinis Lab. The first section is great for reading about how quantum computing works and how superconducting qubits work (though reading the whole thesis is also worth doing) Difficulty: I to A
• Towards practical linear optical quantum computing, another thesis, this one by Mercedes Gimeno-Segovia. This one’s introduction provides a great description of optical quantum computing, and also describes cluster-state quantum computing. A very interesting read. Difficulty: I to A

Simulators

• Quirk — code accessible on Github, many features.
• IBM quantum experience — quite nice now that it’s been updated, includes forum to ask questions and a “wiki” of sorts.