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.

forQF2.jpg

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.

16 thoughts on “The world of hackers and secrets

  1. At least please show some experimental numbers so that you can claim quantum matrix computation is faster……. people are tired of these theoretical quantum computing papers

    • Do you not believe my claim that a Matlab code for the circuit in the figure takes >1ms? I can send you the code 🙂

      As for where did I get the number 1ms for a quantum chip (like IBM quantum experience or D-wave), that’s a topic for a whole new post. Would you be interested in reading about it?

      • Are you kidding me?! Your reply just shows you have no idea on experimental measurements or any experience in high performance computational mathematics. Who will use matlab when he/she is seriously interested in high performance matrix computation? Have you considered paralleization? have you heard about using cache and dram to accelerate matrix multiplication when you are dealing with this trivial sizes? Have you heard about high performance matrix computation library such as cblas or MKL? And you think 1ms for 32×32 matrices is fast?! You gotta be kidding me! You are lack of basic training of experimental computer science.

        Looked at the performance reported here:
        https://software.intel.com/en-us/articles/performance-of-classic-matrix-multiplication-algorithm-on-intel-xeon-phi-processor-system

        Even for 256 x 256 matrix computation, it takes less than 1ms when the software is well optimized for the hardware.

        BTW, 32×32 is really like toy example, and if you tell computational mathematicians about these, they will laugh at you. Seriously.

        • You’re right, this post is not completely serious, I exaggerated some of the points for comedic effect. However, I don’t think you should jump into conclusions about my level of education.
          I’m aware of special matrix multiplication algorithms, and that the reported 1ms was mostly due to slow memory allocation and not the matrix size (which can be seen from Figure 1 of linked article if you look at the MKL performance). I did not want to make my post too complicated, as it’s intended for all audiences. Anyone can learn to use Matlab, and it is used widely, even in performance-intensive tasks. Optimized C-code is costly and has a high barrier of entry (if an undergraduate tries to write it, more often than not he’ll end up underperforming compared to Matlab).
          Also, the Figure 1 in linked article reports the time needed for a single matrix multiplication, while I quoted 1ms as the time to evaluate the whole circuit (n*t multiplications for n – number of qubits, and t – how many gates can be performed until total decoherence). Taking that into account, maybe not 5qubit, but 8qubit quantum computer will beat the performance reported in Fig 1 for 256×256 matrices.

          • I would suggest the author this blog consider the comments seriously. This article just makes quantum computing more embarrasing. People like this author shall learn from their colleague in quantum communication/cryptography who are always making breakthrough via hard experiments. It is disapointing to see the author wasting time bragging about trivial results instead of working hard on doing real useful stuff.

            • I don’t think there’s anything embarrassing in the post. This blog is not only for reports of breakthroughs, it is also for discussion of new directions that the field might have overlooked. If you think that this direction is useless, please provide a constructive criticism instead of shaming me for not working hard enough.

  2. QC is a main JJ provider for entangled microwaves. These can be put into an aircraft and one fired at the ground, looking for a robot digging a bunker with which to print metal robots or make insect drones. Most microwaves will decohere, but a few should slightly alter in polarization passing through matter and air and this will be measurable, maybe even non-destructively, looking at the entangled microwave left in the aircraft. Then you look for AI and robot labs. Then you (a weighted MRI-based vote) decide which technologies should be retired and which should not be invented any time soon. Because AI will learn hacking via examining its own communications, you can’t hide a personal cloak for long. 1000000 metal robots might win without railguns, only 1000 needed to win if they make cloaks. The personal cloak shouldn’t be hidden, it should not be invented.

  3. This blog post is indeed pretty embarrassing. But I think the author is perhaps only a science or even just sci-fi fan without too much knowledge about quantum information. Given the author is not a pro in this area, I don’t think people in the responses above should be this strict. Be nice to people who just want to get to know science!

    • I think the author probably knows quantum physics, it’s just the author has no idea about computing in reality… but I agree with you, be nice to inexperienced people who just started exploring

  4. I enjoyed the critical thinking in the comments above. Doing theory is not the excuse of writing crazy articles in a science blog.

Your thoughts here.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s