Thursday, March 29, 2018

Almost Famous Quantum Polynomial Time

I have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in AFQP if there is a polynomial-time quantum Turing machine Q such that for all inputs x,
  • If x is in L, then Q(x) accepts with high probability.
  • If x is not in L, then Q(x) rejects with high probability.
  • Q(x) only has O(log |x|) quantumly entangled bits as well as a polynomial amount of "deterministic" memory. 
AFQP is meant to capture the state of the art of current quantum technology.

AFQP has several nice properties, capturing the complexity of many open problems.
  1. If BQP is in AFQP then factoring is in BPP.
  2. If one can solve satisfiability in AFQP then the polynomial-time hierarchy collapses.
  3. AFQP is contained in the fifth level of the polynomial-time hierarchy.
  4. If AFQP is in log-space then matching has a deterministic NC algorithm.
  5. Graph isomorphism is in a quasi-polynomial time version of AFQP.
  6. AFQP = PPAD iff Nash Equilibrium has solutions we can find in polynomial time.
The proofs use a clever combination of Fourier analysis and semidefinite programming. 

Where does the name AFQP come from? The authors claim that they didn't name the class after themselves, and instead say it stands for "Almost Famous Quantum Polynomial Time" as it won't get the fame of BQP. More likely it is because it's April the first and I'm feeling a bit Foolish making up a new complexity class that is just P in disguise. 


  1. This is probably obvious but why can't you simulate this model on a classical Turing machine (with polynomial overhead)?

  2. I think that these earlier results of Alagna, showing the distinction between left and right-handedness may be of interest

  3. I can easily prove that the (promise) decision problem languages of BQLOG is in P (just simulate the system then check if the probability to accept is above 2/3). But AFBQP is not yet provably equal to P^BQLOG since it gets the actual probabilistic output of the quantum subsystem. This means that it can use the quantum sub-system to generate random bits. This makes it equal to BPP. So I think that you have some minor errors in your April fools post.