When can Quantum Annealing win

Posted by Hartmut Neven, Director of Engineering

During the last two years, the Google Quantum AI team has made progress in understanding the physics governing quantum annealers. We recently applied these new insights to construct proof-of-principle optimization problems and programmed these into the D-Wave 2X quantum annealer that Google operates jointly with NASA. The problems were designed to demonstrate that quantum annealing can offer runtime advantages for hard optimization problems characterized by rugged energy landscapes.

We found that for problem instances involving nearly 1000 binary variables, quantum annealing significantly outperforms its classical counterpart, simulated annealing. It is more than 10⁸ times faster than simulated annealing running on a single core. We also compared the quantum hardware to another algorithm called Quantum Monte Carlo. This is a method designed to emulate the behavior of quantum systems, but it runs on conventional processors. While the scaling with size between these two methods is comparable, they are again separated by a large factor sometimes as high as 10⁸.

Time to find the optimal solution with 99% probability for different problem sizes. We compare Simulated Annealing (SA), Quantum Monte Carlo (QMC) and D-Wave 2X. Shown are the 50, 75 and 85 percentiles over a set of 100 instances. We observed a speedup of many orders of magnitude for the D-Wave 2X quantum annealer for this optimization problem characterized by rugged energy landscapes. For such problems quantum tunneling is a useful computational resource to traverse tall and narrow energy barriers.

While these results are intriguing and very encouraging, there is more work ahead to turn quantum enhanced optimization into a practical technology. The design of next generation annealers must facilitate the embedding of problems of practical relevance. For instance, we would like to increase the density and control precision of the connections between the qubits as well as their coherence. Another enhancement we wish to engineer is to support the representation not only of quadratic optimization, but of higher order optimization as well. This necessitates that not only pairs of qubits can interact directly but also larger sets of qubits. Our quantum hardware group is working on these improvements which will make it easier for users to input hard optimization problems. For higher-order optimization problems, rugged energy landscapes will become typical. Problems with such landscapes stand to benefit from quantum optimization because quantum tunneling makes it easier to traverse tall and narrow energy barriers.

We should note that there are algorithms, such as techniques based on cluster finding, that can exploit the sparse qubit connectivity in the current generation of D-Wave processors and still solve our proof-of-principle problems faster than the current quantum hardware. But due to the denser connectivity of next generation annealers, we expect those methods will become ineffective. Also, in our experience we find that lean stochastic local search techniques such as simulated annealing are often the most competitive for hard problems with little structure to exploit. Therefore, we regard simulated annealing as a generic classical competition that quantum annealing needs to beat. We are optimistic that the significant runtime gains we have found will carry over to commercially relevant problems as they occur in tasks relevant to machine intelligence.

For details please refer to http://arxiv.org/abs/1512.02206.

Read More..

Launching the Quantum Artificial Intelligence Lab

Posted by Hartmut Neven, Director of Engineering

We believe quantum computing may help solve some of the most challenging computer science problems, particularly in machine learning. Machine learning is all about building better models of the world to make more accurate predictions. If we want to cure diseases, we need better models of how they develop. If we want to create effective environmental policies, we need better models of what’s happening to our climate. And if we want to build a more useful search engine, we need to better understand spoken questions and what’s on the web so you get the best answer.

So today we’re launching the Quantum Artificial Intelligence Lab. NASA’s Ames Research Center will host the lab, which will house a quantum computer from D-Wave Systems, and the USRA (Universities Space Research Association) will invite researchers from around the world to share time on it. Our goal: to study how quantum computing might advance machine learning.

Machine learning is highly difficult. It’s what mathematicians call an “NP-hard” problem. That’s because building a good model is really a creative act. As an analogy, consider what it takes to architect a house. You’re balancing lots of constraints -- budget, usage requirements, space limitations, etc. -- but still trying to create the most beautiful house you can. A creative architect will find a great solution. Mathematically speaking the architect is solving an optimization problem and creativity can be thought of as the ability to come up with a good solution given an objective and constraints.

Classical computers aren’t well suited to these types of creative problems. Solving such problems can be imagined as trying to find the lowest point on a surface covered in hills and valleys. Classical computing might use what’s called “gradient descent”: start at a random spot on the surface, look around for a lower spot to walk down to, and repeat until you can’t walk downhill anymore. But all too often that gets you stuck in a “local minimum” -- a valley that isn’t the very lowest point on the surface.

That’s where quantum computing comes in. It lets you cheat a little, giving you some chance to “tunnel” through a ridge to see if there’s a lower valley hidden beyond it. This gives you a much better shot at finding the true lowest point -- the optimal solution.

We’ve already developed some quantum machine learning algorithms. One produces very compact, efficient recognizers -- very useful when you’re short on power, as on a mobile device. Another can handle highly polluted training data, where a high percentage of the examples are mislabeled, as they often are in the real world. And we’ve learned some useful principles: e.g., you get the best results not with pure quantum computing, but by mixing quantum and classical computing.

Can we move these ideas from theory to practice, building real solutions on quantum hardware? Answering this question is what the Quantum Artificial Intelligence Lab is for. We hope it helps researchers construct more efficient and more accurate models for everything from speech recognition, to web search, to protein folding. We actually think quantum machine learning may provide the most creative problem-solving process under the known laws of physics. We’re excited to get started with NASA Ames, D-Wave, the USRA, and scientists from around the world.

Read More..

A step closer to quantum computation with Quantum Error Correction

Posted by Julian Kelly, Rami Barends, and Austin Fowler, Quantum Electronics Engineers

Computer scientists have dreamt of large-scale quantum computation since at least 1994 -- the hope is that quantum computers will be able to process certain calculations much more quickly than any classical computer, helping to solve problems ranging from complicated physics or chemistry simulations to solving optimization problems to accelerating machine learning tasks.

One of the primary challenges is that quantum memory elements (“qubits”) have always been too prone to errors. They’re fragile and easily disturbed -- any fluctuation or noise from their environment can introduce memory errors, rendering the computations useless. As it turns out, getting even just a small number of qubits together to repeatedly perform the required quantum logic operations and still be nearly error-free is just plain hard. But our team has been developing the quantum logic operations and qubit architectures to do just that.

In our paper “State preservation by repetitive error detection in a superconducting quantum circuit”, published in the journal Nature, we describe a superconducting quantum circuit with nine qubits where, for the first time, the qubits are able to detect and effectively protect each other from bit errors. This quantum error correction (QEC) can overcome memory errors by applying a carefully choreographed series of logic operations on the qubits to detect where errors have occurred.

Photograph of the device containing nine quantum bits (qubits). Each qubit interacts with its neighbors to protect them from error.

So how does QEC work? In a classical computer, we can monitor bits directly to detect errors. However, qubits are much more fickle -- measuring a qubit directly will collapse entanglement and superposition states, removing the quantum elements that make it useful for computation.

To get around this, we introduce additional ‘measurement’ qubits, and perform a series of quantum logic operations that look at the measurement and data qubits in combination. By looking at the state of these pairwise combinations (using quantum XOR gates), and performing some careful cross-checking, we can pull out just enough information to detect errors without altering the information in any individual qubit.

The basics of error correction. ‘Measurement’ qubits can detect errors on ‘data’ qubits through the use of quantum XOR gates.

We’ve also shown that storing information in five qubits works better than just storing it in one, and that with nine qubits the error correction works even better. That’s a key result -- it shows that the quantum logic operations are trustworthy enough that by adding more qubits, we can detect more complex errors that otherwise may cause algorithmic failure.

While the basic physical processes behind quantum error correction are feasible, many challenges remain, such as improving the logic operations behind error correction and testing protection from phase-flip errors. We’re excited to tackle these challenges on the way towards making real computations possible.

Read More..

Hardware Initiative at Quantum Artificial Intelligence Lab

Posted by Hartmut Neven, Director of Engineering

The Quantum Artificial Intelligence team at Google is launching a hardware initiative to design and build new quantum information processors based on superconducting electronics. We are pleased to announce that John Martinis and his team at UC Santa Barbara will join Google in this initiative. John and his group have made great strides in building superconducting quantum electronic components of very high fidelity. He recently was awarded the London Prize recognizing him for his pioneering advances in quantum control and quantum information processing. With an integrated hardware group the Quantum AI team will now be able to implement and test new designs for quantum optimization and inference processors based on recent theoretical insights as well as our learnings from the D-Wave quantum annealing architecture. We will continue to collaborate with D-Wave scientists and to experiment with the “Vesuvius” machine at NASA Ames which will be upgraded to a 1000 qubit “Washington” processor.

Read More..

Simulating fermionic particles with superconducting quantum hardware

Posted by Rami Barends and Julian Kelly, Quantum Electronics Engineers and John Martinis, Research Scientist

Digital quantum simulation is one of the key applications of a future, viable quantum computer. Researchers around the world hope that quantum computing will not only be able to process certain calculations faster than any classical computer, but also help simulate nature more accurately and answer longstanding questions with regard to high temperature superconductivity, complex quantum materials, and applications in quantum chemistry.

A crucial part in describing nature is simulating electrons. Without electrons, you cannot describe metals and their conductivity, or the interatomic bonds which hold molecules together. But simulating systems with many electrons makes for a very tough problem on classical computers, due to some of their peculiar quantum properties.

Electrons are fermionic particles, and as such obey the well-known Pauli exclusion principle which states that no fermions in a system can occupy the same quantum state. This is due to a property called anticommutation, an inherent quantum mechanical behavior of all fermions, that makes it very tricky to fully simulate anything that is composed of complex interactions between electrons. The upshot of this anticommutative property is that if you have identical electrons, one at position A and another at position B, and you swap them, you end up with a different quantum state. If your simulation has many electrons you need to carefully keep track of these changes, while ensuring all the interactions between electrons can be completely, yet separately tunable.

Add to that the memory errors caused by fluctuation or noise from their environment and the fact that quantum physics prevents one from directly monitoring the superconducting quantum bits (“qubits”) of a quantum computer directly to account for those errors, and youve got your hands full. However, earlier this year we reported on some exciting steps towards Quantum Error Correction - as it turns out, the hardware we built isnt only useable for error correction, but can also be used for quantum simulation.

In Digital quantum simulation of fermionic models with a superconducting circuit, published in Nature Communications, we present digital methods that enable the simulation of the complex interactions between fermionic particles, by using single-qubit and two-qubit quantum logic gates as building blocks. And with the recent advances in hardware and control we can now implement them.

We took our qubits and made them act like interacting fermions. We experimentally verified that the simulated particles anticommute, and implemented static and time-varying models. With over 300 logic gates, it is the largest digital quantum simulation to date, and the first implementation in a solid-state device.

Left: Model picture with four fermionic modes in two sites. The modes are occupied or unoccupied. For example, we can start with two fermionic particles in the right well, by occupying the blue and green mode. If the particles repel each other, theres a good chance that one of the them will hop to the left well through the process of quantum tunneling through the barrier. It will then occupy the red or purple mode. This interplay of on-site interaction and hopping lies at the core of describing processes in physics and chemistry, ranging from the conductivity of metals to the binding between atoms in molecules. Right: The false-colored cross-shaped structures are the superconducting quantum bits. The colors correspond to the modes, so if we have two fermionic particles in the blue and red modes, the rightmost two quantum bits are excited.

Coming up with an efficient sequence of logic gates that can accurately model the interactions for systems of fermions wasn’t easy. So we teamed up with Dr. Lucas Lamata, M.Sc. Laura García-Álvarez, and Prof. Enrique Solano from the QUTIS group at the University of the Basque Country (UPV/EHU) in Bilbao, Spain, who are experts in constructing algorithms and translating them into the streams of logic gates we can implement with our hardware.

For the future, digital quantum simulation holds the promise that it can be run on an error-corrected quantum computer. But before that, we foresee the construction of larger testbeds for simulation with improvements in logic gates and architecture. This experiment is a critical step on the path to creating a quantum simulator capable of modeling fermions as well as bosons (particles which can be interchanged, as opposed to fermions), opening up exciting possibilities for simulating physical and chemical processes in nature.

Read More..