The Big Data Challenge.

quantum leap

Like most people, I am sick of hearing about “big data.” First of all, there is no such thing as big data – there’s just data. Second, having a lot of data doesn’t mean anything. It’s what you do with the data that matters.

In my role as math nerd here at bloomfield knoble, I am often asked by people about what they should do with their data. My first response is always, “sort it.” You’d be amazed how many blank stares that generates. I will then, ad nauseam, explain how data should be structured in order to be analyzed and interpreted – and this is where the first sign of trouble begins. See, storing data is easy and not very expensive. I have about 10 TB in storage sitting on my desk right now. It’s cheap and works seamlessly with my desktop, making it easy to move files and such. People think that sorting data will be easy, but moving files and working with them are two different things. People are often shocked when they try to actually work with data. Most people don’t have a computer with the power and resources to even tackle the project, let alone the software necessary to actually determine correlations.

Just when it seems like all hope is lost and that crunching data will have to be outsourced to giants like IBM, Amazon and Google, along comes a light at the end of a dark data tunnel – quantum computing. Yes, dear readers, it’s been too long since I’ve written about quantum computing (or, as I like to call it, quamputing). I’m just using big data as a cover to gush on quantum computing.

According to Jacob Aron writing in New Scientist magazine, the first piece of software to show the potential of quantum computing has finally been run on a real machine, 20 years after it was initially dreamed up. Although it doesn’t do anything useful on its own, implementing the algorithm could lead to more practical computers powered by the strange properties of quantum mechanics. Quantum computers should be much faster than ordinary ones, but only at tasks for which there is a quantum algorithm – software that exploits the computer’s quantum nature. Without these algorithms, quantum computers are just regular computers that are much harder to build.

One of the best-known pieces of quantum software is Shor’s algorithm, which factorizes large numbers into their prime components – a notoriously slow and difficult problem to solve classically. Shor’s algorithm has been run in a limited way using photons sent through the air and on silicon chips, but a full-blown quantum computer capable of running it could threaten online encryption, which relies on large primes. Designing an algorithm that takes advantage of a quantum computer is tricky, so there aren’t many around. In 1994, Daniel Simon, then at the University of Montreal, Canada, came up with one. Crucially, it was the first to show that a quantum computer could crack a problem exponentially faster than an ordinary computer.

Ironically, Simon was trying to prove quantum computers could never be useful but he stumbled across a problem that showed the exact opposite. Imagine you feed a string of bits, like 0101, into a black box and get another string, like 1100, out in return. there are a finite number of possible outputs, but you don’t know how they are produced. Simon’s problem asks: does the black box give a unique output for every possible input, or do some inputs give a common output? Simon’s algorithm for solving it inspired the more useful Shor’s algorithm and the field of quantum computing as a whole.

Enter Mark Tame at the University of KwaZulu-Natal in Durban, South Africa, and his colleagues. They used a “one-way” quantum computer – one that uses up some of its qubits to solve a two-bit version of Simon’s problem, the simplest possible. More specifically, they state, “We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon’s Problem – a black box period-finding problem which has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version’s black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon’s Problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.”

Tame’s quantum computer only needed an average of two runs to succeed, while an ordinary computer needed an average of slightly less than three runs – the first step in an exponential speed-up in line with theoretical predictions. “For me it has been like finding the missing piece of a jigsaw and putting it in its place to complete the picture,” says Tame. While most people agree that the run has little practical value, it isn’t the speedup that matters as much has what it could lead to.