In a series of posts, we introduced various **quantum computing** concepts:

- How information and quantum mechanics are related ?
- What is quantum computing ?
- What are Bell states ?
- What is quantum teleportation ?
- What is quantum error correction ?
- What are topological quantum computer ?

In addition to these concepts, we devoted two posts to the very crucial topic that is **complexity**:

In a recent paper, computer scientists Ran Raz and Avishay Tal **rocked the world of quantum complexity** so much it is now time for an update on that subject !

**Back to complexity classes**

One of the purposes of theoretical computer science is to sort problems into complexity classes. Quoting Quanta Magazine, a complexity class “*contains all problems that can be solved within a given resource budget, where the resource is something like time or memory.*”

In a previous post, we have introduced the two most famous complexity classes:

**P**: The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time.**P**is all the problems that a classical computer can solve quickly (for example: “Is this number prime?” belongs to**P**).**NP**: The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time.**NP**is all the problems that classical computers can’t necessarily solve quickly, but for which they can quickly verify an answer if presented with one. (for example: “What are its prime factors?” belongs to**NP**).

Also, within the NP class, we introduced **NP-complete** and NP-hard problem (a problem is said to be **NP-hard** if an algorithm for solving it can be translated into one for solving any NP-problem), as well as NP-intermediate (**NPI**) class (problems in the complexity class NP but that are neither P nor NP-complete).

**co-NP** is the complexity class which contains the complements of problems found in NP. In other terms, class of problems for which there is a polynomial-time algorithm that can verify counterexamples.

Determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today:

**Quantum complexity**

In 1993 computer scientists Ethan Bernstein and Umesh Vazirani defined a new complexity class called **BQP** (for Bounded-error Quantum Polynomial time): the complexity class of decision problems that can be solved with 2-sided error on a quantum Turing machine in polynomial time.

They defined this particular class to contain all the decision problems that quantum computers can solve efficiently. They also proved that quantum computers can solve all the problems that classical computers can solve : **BQP** contains all the problems that are in **P**.

A central task of quantum computing theory is to understand how **BQP** fits in with classical complexity classes. That is why the boundaries of **BQP**, sketched in the following diagram, are uncertain:

So far, we know that:

**P**sits in**BQP****BQP**sits in**PSPACE**- Boundaries of
**BQP**(relative to**NP**) are uncertain

**Polynomial hierarchy**

**polynomial hierarchy**is a hierarchy of complexity classes that generalize the classes

**P**,

**NP**and

**co-NP**to oracle machines. An

**oracle machine**is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box (called an

**oracle)**, which is able to solve certain decision problems in a single operation.

The complexity class **PH** is the union of all complexity classes in the **Polynomial Hierarchy**. **PH** is the is a generalization of **NP** to allow multiple quantifiers such as ∃ (i.e. there exists), ∀ (i.e. for all), etc. (see second order logic for details).

You can think of **PH** as the class of all problems classical computers could solve if **P** turned out to equal **NP**.

In other words, to compare **BQP** and **PH** is to “*determine whether quantum computers have an advantage over classical computers that would survive even if classical computers could solve many more problems than they can today***“** [Quanta Magazine].

**Using oracle separation to distinguish BQP from PH**

Up to now, there were **some evidence** that **BQP was not contained in PH**. This result is **now proven** by Ran Raz and Avishay Tal.

The best way to distinguish between two complexity classes is to find a problem that is provably in one and not the other.

If you want a problem that is in **BQP** but not in **PH**, you have to identify something that “*by definition a classical computer could not even efficiently verify the answer, let alone find it*,” (Scott Aaronson).

The first step was the introduction of the concept of “forrelation” (also known as *Fourier checking*) by Scott Aaronson and Andris Ambainis. See for example:

The problem to be solved is the following:

- Imagine two random number generators (
*f*and*g*), each producing a sequence of bits - Forrelation estimates the correlation between
*f*and the Fourier transform of*g*(are the two sequences completely independent from each other, or are they related in a hidden way)

It was then proved in 2010 that forrelation belongs to **BQP**. What is left was the hardest step: **proving that forrelation is not in PH**.

To distinguish between complexity classes like **BQP** and **PH**, one would like be to measure the computational time required to solve a problem in each. Unfortunately, nobody has a clear understanding of how to measure actual computation time.

When the thing they’d really like to prove is beyond their reach, computer scientists often resort to **oracles**. They measure something else that they hope will provide insight into the computation times they can’t measure: they work out the number of times a computer needs to consult an oracl” in order to come back with an answer.

We can get an understanding of complexity by allowing both machines access to the same oracle and seeing what we can separate. In our case, the problem is to figure out whether two random number generators are secretly related:

- You can ask the oracle questions such as “What’s the sixth number from each generator?”.
- Then you compare computational power based on the number of hints each type of computer needs to solve the problem. The computer that needs more hints is slower.

The paper published by Ran Raz and Avishay Tal shows that quantum computer need just one hint, while even with unlimited hints, there’s no algorithm in PH that can solve the problem.

“*This means there is a very efficient quantum algorithm that solves that problem*,” said Raz. “*But if you only consider classical algorithms, even if you go to very high classes of classical algorithms, they cannot.*”

**Quantum and classical computers exist in a different computational realm**

This establishes that with an oracle, Fourier checking (forrelation) is **a problem** that is in **BQP but not in PH**. This is big, so let’s repeat it : for the first time, **a problem is found to be in BQP but not in PH**:

To finish this update, let’s quote Quanta Magazine: “*The work provides an ironclad assurance that quantum computers exist in a different computational realm than classical computers (at least relative to an oracle). Even in a world where P equals NP […] Raz and Tal’s proof demonstrates that there would still be problems only quantum computers could solve.* *Even if P were equal to NP, even making that strong assumption,” said Fortnow, “that’s not going to be enough to capture quantum computing.*”

Note: A few paragraphs and illustrations of this post are based on Quanta Magazine.