It may sound hard to believe but computer scientists all over the world have searched long and hard to find the type of problem which only a quantum computer could solve.
After years of trying, they have finally found a problem that no possible future version of a classical computer can solve.
In the very early stages of the study of quantum machines, various computer scientists often posed questions whose answers they already knew would do nothing but reveal something profound and very deep regarding the potential power of futuristic machines that we know today as quantum computers.
Now, almost half a century later, computer scientists have done all but solve that problem.
Computer scientists Avishay Tal and Ran Raz posted an online paper about two months ago in which they provided vigorous evidence that the latest quantum machines did actually possess the level of computing power that was beyond anything and everything a classical computer machine would ever have the opportunity of achieving.
Ran Raz who works as a professor at the Princeton University and also at the Weizmann Institute of Science (Israel) and Avishay Tal, who is a Stanford University postdoctoral fellow, defined a very particular type of computational problem.
Setting aside a certain caveat, they proved via their paper that quantum machines had the capability to handle a given problem very efficiently while, for the same problem, traditional machines would actually bog down, get stuck and expend resources forever in making attempts to solve the problem.
As mentioned at the top as well, for more than 25 years (since 1993), computer scientists have tried hard to look for the type of problem which would prove quantum’s lead over traditional machines.
The year 1993 represented the first year when computer scientists managed to define a very special class of problems.
They called these problems BQP complexity class problems.
This class encompassed all the problems that only quantum machines have the ability to solve.
Ever since doing that, computer scientists have also tried to contrast the BQP type of problems with another special class of problems that the community now knows as PH.
This class of problems encompasses each and every given problem that a classical computer can work on and possibly solve.
Readers should note that classical computers, in this case, represent all classical computers.
Even the unfathomably advanced classical computers that some futuristic civilization would engineer.
To actually make that kind of contrast happen, computer scientists had to depend on searching and finding a problem which they could prove to be present in BQP but, of course, not in the PH type.
According to their recent research paper, Tal and Raz have managed to find success in doing that.
Before moving ahead though, it is true that their results do not really put quantum machines in an elevated position over any and all classical machines.
At least, not in a practical sense.
Why is that?
Well, one reason (amongst a host of reasons) is that theoretical computer scientists had enough knowledge about how quantum machines could solve any given problem that a classical machine could.
The other reason is that engineers still haven’t found a way to build a quantum computer that is actually of any use.
What Tal and Raz’s research paper does demonstrate is that classical computers and quantum machines really are in a category of their own.
The paper also tries to demonstrate that quantum machines would still have enough about them to stand beyond all classical computers even in a given world where classical machines have succeeded beyond all expectations and realistic dreams.
Quantum Machines and Classes
One of the basic tasks that theoretical computer scientists have to perform on a regular basis is to sort different problems into various complexity classes.
What is a complexity class?
Well, essentially it contains each and every problem that is solvable within a particular resource budget.
What is the “resource” here?
The resource here may be memory or time.
To take an example, theoretical computer scientists have managed to find a very efficient algorithm in order to test whether a given number is actually a prime or not.
What they have not managed to find is an equally efficient algorithm that enables them to identify and find a given large number’s prime factors.
Hence, theoretical computer scientists have this belief that the two above-mentioned problems actually belong to two different complexity classes.
With that said, it is also true that they have not managed to prove that these problems actually do belong to two different complexity classes.
Now, as mentioned before, there are many complexity classes.
Two of these complexity classes that have gained the most popularity are NP and P.
Let’s discuss P first.
P is the complexity class that a given classical machine has the ability to solve pretty quickly.
These problems come in the form of whether the given number is prime or not and others.
Such problems, as obvious, belongs to the P complexity class.
The NP complexity class consists of all the problems that a given classical computer machine doesn’t have the ability to necessarily solve fairly quickly but have enough power to verify, in a relatively short period of time, an answer if these machines are presented with such a problem.
Such problems include ones relating to finding the prime factors of a given number.
These problems belong to the NP complexity class.
Theoretical computer scientists have this belief that NP and P are two distinct complexity classes.
However, for computer scientists, going out, working and actually proving that these two classes are indeed distinct is, currently, the most important and hardest open problem in the computer science field.
Back in 1993, theoretical computer scientists Umesh Vazirani and Ethan Bernstein managed to defined BQP, a new and distinct complexity class.
BQP stood for bounded-error quantum polynomial time.
Vazirani and Bernstein defined the new BQP class to actually contain each and every decision problem that quantum machines could solve in an efficient manner.
What are decision problems/
Decision problems are problems that have a yes or no answer.
Interestingly enough, at around the same time, these two computer scientists also managed to prove that quantum machines could solve each and every given problem which classical machines could solve.
In simpler terms, each and every given problem that exists in BQP also exists in the P complexity class.
Some believe that thinking about these “complexity classes” becomes much easier with the help of examples.
Let’s go through the traveling salesman problem.
This problem basically asks if there exists a perfect path right through some random number of cities which is actually shorter than some given distance.
Such a problem, according to computer scientists, is an NP problem.
However, a more difficult and complex problem basically asks if that shortest path through a random number of cities is exactly equal to that distance.
Such a problem is a PH complexity class problem.
With that said, it is also true that computer scientists so far have not managed to determine whether the problems contained in BQP consists of problems which are also found in another complexity class of problems that the community knows as PH.
PH, is a short form, of the term polynomial hierarchy.
In essence, PH or Polynomial hierarchy is actually a generalization of NP.
What does that mean exactly?
That means, PH contains each and every single problem that one would get if one started with a specific problem in NP and made that problem a bit more complex via layers of qualifying statements such as “for all” and “there exists.”
Generally speaking, the classical machines we have today don’t have the ability to solve the majority of the problems that are found in PH.
However, readers would do well if they thought of PH problems as that particular class of problems which classical machines could potentially solve but only if P eventually turned out to be equal to NP.
To put it in simpler terms, when scientists compare PH and BQP, they actually do it in order to precisely determine whether the new machines we know as quantum computers have an edge (or advantage) over the older machines we call as classical computers even if we assume that classical machines could potentially and rather unexpectedly gain the ability to solve a ton of more problems than they are able to solve today.
According to a theoretical computer scientist at the University of Texas Austin, Scott Aaronson, among the most basic of classical complexity classes, PH is one.
He also said that the community sort of wanted to know where, in the world of classical complexity theory did quantum computing fit in.
One of the best ways to make a distinction between two given complexity classes is to search for and find a particular problem that is actually provably in one complexity class but not so in the other complexity class.
Even with that, because of a combination of technical and fundamental obstacles, an effort to find such a specific problem has proved itself quite a challenge.
According to Anderson if one wanted to solve a problem that was present in the BQP complexity class but not in the PH complexity class, then one would have to identify an aspect of the problem or something which by definition a given classical machine could not even verify the exact answer to in an efficient manner, let alone finding the actual answer.
He further added that setup actually ruled out a good number of problems that researchers and scientists thought about today in the field of computer science.
Oracle: Ask it questions
Let’s take a look at a problem to understand complexity classes and how difficult it is to distinguish them.
First, imagine that someone has a set of two random number generators.
Now, imagine that each of those random number generators produced a sequence of digits.
With that in place, the question that the computer has to solve is this:
Are the two given sequences generated via the random number generators completely independent with respect to each other?
Or are these two randomly generated sequences somehow related in a way that is hidden.
It is entirely possible that one given random sequence of numbers is actually a Fourier transform of the second random sequence of numbers.
Back in the year 2009, Scott Aaronson managed to introduce the above-mentioned Forrelation problem.
He also managed to prove that the problem actually belonged to the BQP complexity class.
With that, the harder of the two steps was left:
To try and prove that the forrelation problem did not exist in the PH complexity class.
This “second step” problem is exactly what Tal and Raz have managed to do in one specific sense.
Their research paper has achieved what the community calls a black box or “oracle” separation between the PH complexity class and the BQP complexity class.
Of course, this kind of result is pretty common in the field of computer science.
It is also the kind of result that computer science researchers have an inclination of resorting to when the exact thing that they would unquestionably like to prove is actually something that is beyond their current reach.
With that said, in reality, the best of the best method to successfully distinguish between different complexity classes such as PH and BQP is to simply measure (accurately) the amount of computational time that is required to solve a specific problem that belongs to each class.
According to a computer scientists at the University of Toronto, Henry Yuen, currently, theoretical computer scientist didn’t actually have an above-average and sophisticated understanding of actual computational time.
Moreover, they also did not have the ability to measure that computational time.
So what do theoretical computer scientists do instead?
They being work on measuring something else.
Something which these computer scientists hope would provide them with an insight into the elusive computation times that they are simply unable to measure.
In other words, these computer scientists shift their work to determine the number of times a given computer machine has the need to consult a black box (or oracle) for the purposes of coming back with an accurate answer to a specific problem.
But what is the oracle?
Fully describing what an oracle is, it would take a book rather than an article.
However, for the purposes of this piece, readers should understand the “oracle” as a giver of hints.
One more thing, no one really knows how the oracle comes up with all the hints it gives to the computer machine, but what one must know is that these hints are more than reliable.
Assuming that the problem a computer is trying to work out is whether there is a secret relationship between two random number generators, then the computer has the option of asking the black box (or the oracle) questions like “what is the eighth number from each random number generator?”
After that one can compare the actual computational power which is based on the exact number of oracle-given hints that each type of machine needed in order to solve the given problem.
Needless to say, the machine which requires more number of oracle hints is the one that is the slower of the two.
According to Tal, in many senses computer scientists understand such a model a lot better.
Because such a model talks in a lot more detail about the actual information rather than just computation.
The new research paper from Tal and Raz successfully proves that a classical computer would require far more hints than a quantum computer in order to solve the aforementioned forrelation problem.
More specifically though, a quantum computer (according to the research paper) only required a single hint.
On the other hand, even with an unlimited number of hints, computer scientists still do not have an algorithm in PH complexity class which has the ability to solve the aforementioned problem.
Raz recently stated that this meant there was an extremely efficient quantum algorithm which solved the given problem.
He also said that if one only considered classical machine algorithms, and even if one went to the highest classes of classical machine algorithms, classical machines did not have the ability to solve such problems.
Such questions and other problems establish with the help of a black box or oracle that problems such as forrelation belong to the BQP complexity class but not to the PH complexity class.
It is also interesting to note that Tal and Raz managed to achieve the exact same result almost half a decade ago back in 2014.
However, back then, they did not manage to complete one more step in their quest to find the proof of their assertion.
Of course, that changed when Tal heard about pseudorandom number generators on a new research paper talk.
There he realized that paper mentioned techniques which would definitely help him and Raz to actually finish their own proof.
According to Tal, that new research paper was the actual missing piece in their own proof.
After Tal and Raz managed to prove that PH and BQP were, in fact, separate complexity classes, the news circulated fairly quickly.
A computer scientist at Georgia Tech, Lance Fortnow, wrote (just a day after Tal and Raz posted their own research paper) that the quantum complexity world had started to rock.
Tal and Raz’s work actually provided the community with ironclad assurance that classical computers and quantum computers actually existed in entirely different computational realms.
That is true at least when it comes to taking hints from the oracle and solving problems.