About hmmmjenia

Jenia Mozgunov, a graduate of IQI, with a focus in mathematical physics

The world of hackers and secrets

I’m Evgeny Mozgunov, and some of you may remember my earlier posts on Quantum Frontiers. I’ve recently graduated with a PhD after 6 years in the quantum information group at Caltech. As I’m navigating the job market in quantum physics, it was only a matter of time before I got dragged into a race between startups. Those who can promise impressive quantum speedups for practical tasks get a lot of money from venture capitalists. Maybe there’s something about my mind and getting paid: when I’m paid to do something, I suddenly start coming up with solutions that never occurred to me while I was wandering around as a student. And this time, I’ve noticed a possibility of impressing the public with quantum speedups that nobody has ever used before.

Three former members of John Preskill’s group, Gorjan Alagic, Stacey Jeffery and Stephen Jordan, have already proposed this idea (Circuit Obfuscation Using Braids, p.10), but none of the startups seems to have picked it up. You only need a small quantum computer. Imagine you are in the audience. I ask you to come up with a number. Don’t tell it out loud: instead, write it on a secret piece of paper, and take a little time to do a few mathematical operations based on the number. Then announce the result of those operations. Once you are done, people will automatically be split into two categories. Those with access to a small quantum computer (like the one at IBM) will be able to put on a magic hat (the computer…) and recover your number. But the rest of the audience will be left in awe, with no clue as to how this is even possible. There’s nothing they could do to guess your number based only on the result you announced, unless you’re willing to wait for a few days and they have access to the world’s supercomputing powers.

So far I’ve described the general setting of encryption – a cipher is announced, the key to the cipher is destroyed, and only those who can break the code can decipher.  For instance, if RSA encryption is used for the magic show above, indeed only people with a big quantum computer will be able to recover the secret number. To complete my story, I need to describe what the result that you announce (the cipher) looks like:

A sequence of instructions for a small quantum computer that is equivalent to a simple instruction for spitting out your number. However, the announced sequence of instructions is obfuscated, such that you can’t just read off the number from it.

You really need to feed the sequence into a quantum computer, and see what it outputs. Obfuscation is more general than encryption, but here we’re going to use it as a method of encryption.

Alagic et al. taught us how to do something called obfuscation by compiling for a quantum computer: much like when you compile a .c file in your CS class, you can’t really understand the .out file. Of course you can just execute the .out file, but not if it describes a quantum circuit, unless you have access to a quantum computer. The proposed classical compiler turns either a classical or a quantum algorithm into a hard-to-read quantum circuit that looks like braidsBraid_1000.gif. Unfortunately, any obfuscation by compiling scheme has the problem that whoever understands the compiler well enough will be able to actually read the .out file (or notice a pattern in braids reduced to a compact “normal” form), and guess your number without resorting to a quantum computer. Surprisingly, even though Alagic et al.’s scheme doesn’t claim any protection under this attack, it still satisfies one of the theoretical definitions of obfuscation: if two people write two different sets of instructions to perform the same operation, and then each obfuscate their own set of instructions by a restricted set of tricks, then it should be impossible to tell from the end result which program was obtained by whom.


Theoretical obfuscation can be illustrated by these video game Nier cosplayers: when they put on their wig and blindfold, they look like the same person. The character named 2B is an android, whose body is disposable, and whose mind is a set of instructions stored on a server. Other characters try to hack her mind as the story progresses.

Quantum scientists can have their own little world of hackers and secrets, organized in the following way: some researchers present their obfuscated code outputting a secret message, and other researchers become hackers trying to break it. Thanks to another result by Alagic et al, we know that hard-to-break obfuscated circuits secure against classical computers exist. But we don’t know how the obfuscator that produces those worst-case instances reliably looks like, so a bit of crowdsourcing to find it is in order. It’s a free-for-all, where all tools and tricks are allowed. In fact, even you can enter! All you need to know is a universal gate set H,T = R(π/4),CNOT and good old matrix multiplication. Come up with a product of these matrices that multiplies to a bunch of X‘s (X=HT⁴H), but such that only you know on which qubits the X are applied. This code will spit out your secret bitstring on an input of all 0’es. Publish it and wait until some hacker breaks it!

Here’s mine, can anyone see what’s my secret bitstring?

Obfuscated circuit.png

One can run it on a 5 qubit quantum computer in less than 1ms. But if you try to multiply the corresponding 32×32 matrices on your laptop, it takes more than 1ms. Quantum speedup right there. Of course I didn’t prove that there’s no better way of finding out my secret than multiplying matrices. In fact, had I used only even powers of the matrix T in the picture above, then there is a classical algorithm available in open source (Aaronson, Gottesman) that recovers the number without having to multiply large matrices.

I’m in luck: startups and venture capitalists never cared about theoretical proofs, it only has to work until it fails. I think they should give millions to me instead of D-wave. Seriously, there’s plenty of applications for practical obfuscation, besides magic shows. One can set up a social network where posts are gibberish except for those who have a quantum computer (that would be a good conspiracy theory some years from now). One can verify when a private company claims to sell a small quantum computer.

I’d like to end on a more general note: small quantum computers are already faster than classical hardware at multiplying certain kinds of matrices. This has already been proven for a restricted class of quantum computers and a task called boson sampling. If there’s a competition in matrix multiplication somewhere in the world, we can already win.

A detective with a quantum helper

Have you ever wanted to be incredibly perceptive and make far-reaching deductions about people? I have always been fascinated by spy stories, and how the main character in them notices tiny details of his surroundings to navigate life-or-death situations. This skill seems out of reach for us normal people; you have to be “a high-functioning sociopath” to memorize all existing data on behavior, clothes choices and forensic science. Of course I’m referring to:
Small details help Sherlock figure out what did the woman do to meet such a sad end
Yet in the not too distant future, a computer may help you become a brilliant detective (or a scheming villain) yourself! The first step is noticing the details, which is known in machine learning as the classification task. Here is a pioneering work that somewhat resembles the above picture, only it’s done by a computer:
A computer spits out a sentence (read down) describing what's in the picture. Work by Stanford group.

The task for the computer here was to produce a verbal description of the image. There are thousands of words in the vocabulary, and a computer has to try them in different combinations to make a sensible sentence. There is no way a computer can be given an exhaustive list of correct sentences with examples of images for each. That kind of list would be a database bigger than the earth (as one can see just by counting the number of combinations). So to train the computer to use language like in a picture above, one only possesses a limited set of examples – maybe a few thousand pictures with descriptions. Yet we as humans are capable of learning from just seeing a few examples, by noticing the repeating patterns. So the computer can do the same! The score next to each word above is an estimate based on those few thousand examples of how relevant is the word “tennis” or “woman” to what’s in the box on the image. The algorithm produces possible sentences, scores them, and then selects the sentence with the highest total score.

Once the classification task is done, one needs to use all the collected information to make a prediction – as Sherlock is able to point out the most probable motive in the first picture, we also want to predict a piece of very personal information: we’d like to know how to start up a conversation with that tennis player.

Humans are actually good at classification tasks: with luck, we can notice and type in our cellphone all the details the predictor will need, like brand of clothing, hair color, height… though computers recently became better than humans at facial expression recognition, so we don’t have to trust ourselves on that anymore. Finally, when all the data is collected, most humans will still say only generic advice to you on conversation starters. Which means we are very bad at prediction tasks. We don’t notice the hidden dependencies between brand of clothes and sense of humor. But such information may not hide from the all-seeing eye of the machine learning algorithm! So expect your cellphones to give you dating advice within 10 years… 

Now how do quantum computers come into play? Well if you look at your search results, they are still pretty irrelevant most of the time. Imagine you used them as conversation starters – you’ll embarrass yourself 9 out of 10 times! To make this better, a certain company needs more memory and processing power. Yet most advanced deep learning routines remain out of reach, just because there are exponentially many hidden dependencies one would need to try and reject before the algorithm finds the right predictor. So a certain company turns to us, quantum computing people, as we deal with exponentially hard problems notoriously well! And indeed, quantum algorithms make some of the machine learning routines exponentially faster – see this Quantum Machine Learning article, as well as a talk by Seth Lloyd for technical details. Some anonymous stock trader is already trying to intimidate their fellow quants (quantitative analysts) by calling the top trading system “Quantum machine learning”. I think we should appreciate his sense of humor and invest into his algorithm as soon as Quantiacs.com opens such functionality. Or we could invest in Teagan from Caltech – her code recently won the futures contest on the same website.

Making sci-fi teleportation sound less crazy


Laser beam bending due to a change in the speed of light in water.

If you ever wanted to see a sci-fi plot that expertly applied advanced physical concepts so that with a bit of imagination teleporting a human was not as unbelievable as most of the teleportation scenarios we see in the movies, keep reading.

Years ago, when I was still in Russia, I was working on a back-story for a sci-fi game I was playing with friends. In the game, players were given stones (from Mars!) that could change the fundamental constants of nature: electron charge e, speed of light c and Planck constant h. I had already worked out the effects these stones would produce on the space around them (I suggest it as an exercise to the nerdy reader – once you are done thinking about it, see my answer below), so my next task was to envision a big scientific project centered around those stones, with a solid foundation on real physics and a portal to Mars as a final goal. As it turned out, some unforeseen consequences included blowing up the whole lab and scattering the stones in the nearby forest. That’s the back-story.

It all worked beautifully on paper. I imagined that materials could be programmed to obey different values of fundamental constants. These Martian stones were supposed to be the first encounter humanity had with matter where such effects could be observed and studied. The effects extended to a region around the stone, with weird things happening on the boundary of that region. For one thing, energy was not conserved in the vicinity of these stones.

Now having control over e, c and h, the scientists would leverage this new-found power to try to move the fine structure constant e^2/(\hbar c) to what is known as the Landau pole. Such a feat would result in infinitely strong interactions between particles, so that the energetic content of space-time would jump through the roof and a black hole would form. If one was lucky, even a traversable wormhole would form, which is what the scientists were hoping for, because back on Mars these things could have formed naturally, and the lab wormhole would connect to the Martian network.

If you’ve read all this and are asking yourself “What just happened?”, see all the physical concepts explained below: Continue reading

Quantum = Pink

Need we say more?

What color do you imagine when you close your eyes and think “Quantum”? If you are to buy a case for your quantum computer, have you already picked your favorite color? (Okay, maybe it’s too early for that.)
Below I argue that the collective unconscious has already made the choice for you: it is going to be pink.


Fear not. We will easily differentiate ourselves from warm and fluffy pink slippers. Our color is pink on black. Closer to purple, actually. We have good heritage: purple with white was the color of kings. But kings are no more, so let’s admit it: People think that “spooky” quantum phenomena have a purple glow around them. The disaster movie “Quantum Apocalypse” has a mysterious purple vortex approach Earth. Sci-fi now has “quantum cannons” shooting pink aura at the enemies, unleashing the chaos of uncertainty. You can’t fly your battlecruiser if you’re no longer certain you still have a battlecruiser.
Continue reading

All those different things called Gauge theories.

Generations of kids had their first encounter with the explanation to the question: What does matter consist of? Atoms -> protons -> quarks. There is a certain pleasure in explaining this, regardless of your physics background. Just like a soldier polishes every new medal he gets, the story about elementary particles gets more exciting with every new ‘magic number’ introduced. Indeed, why 3 colors for quarks? A lay person would think that the inspiration came from the RGB (red-green-blue) colors in a TV tube. However, what physicists really did was try to say a new word in the language of gauge theories. And colored quarks was one of the first words one can say when learning to speak such a language: U(1), SU(2), SU(3)! The very third word.

So why don’t we try to share a scientific excitement about gauge theories?
Continue reading