By Lukasz Cincio
In a hot auditorium deep in the Laboratory’s Physics Building at Los Alamos National Laboratory, college physics and computing students, veteran scientists and esteemed Laboratory fellows file in after lunch for the Director’s Colloquium, as they have done for decades. The well-worn fabric seats and wood panel walls have seen some of the world’s most influential scientists speak.
But this lecture is different and a sense of anticipation fills the crowd. Quantum computing guru Scott Aaronson from the University of Texas at Austin is giving the final lecture in the Quantum Computing Summer School, a new program aimed at building a global workforce capable of working on the computers of the future — quantum computers.
Aaronson talks about the P versus NP problem, which asks whether a problem whose solution can be verified quickly can also be solved quickly. A seemingly simple question, it has yet to be answered.
But the person who does find an answer will be $1 million richer as it is one of the Millennium Prize Problems — a set of problems so difficult that most remain unsolved after decades. The people who do eventually solve them will receive prize money from the Clay Mathematics Institute.
The P versus NP problem is about classical computation, the kind of digital computers we’re all familiar with, from our laptops to our phones, but it has implications for quantum computers, too.
By now, everyone has heard of quantum computers and the potential they have to shape the future.
From faster financial analysis to better medicine for cancer treatment, quantum computers could solve bigger problems much faster than classical computers.
So what makes a quantum computer quantum, and why do they have so much potential?
To understand this, let’s take a very basic look at how classical computers work. A classical computer uses bits that are 0s or 1s, and transmits them via electrical impulses through logic gates.
Quantum computers, on the other hand, do not have any bits — they have quantum bits, or qubits. Unlike its classical counterpart, a qubit can be in a superposition of 0 and 1, meaning that, for a given…