Home Online Mathematical Communication Computational Complexity Almost Famous Quantum Polynomial Time

Almost Famous Quantum Polynomial Time

Computational Complexity 2018-04-01

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.