Skip to main content

Questions tagged [quantum-complexity-theory]

Filter by
Sorted by
Tagged with
3 votes
0 answers
55 views

Are there approximability schemes for NP-Hard problems using quantum algorithms? [duplicate]

I'm looking into some parts of Quantum Complexity Theory and was wondering if we have any approximability schemes for NP-Hard problems using quantum algorithms. I was unable to find any literature on ...
LukasM's user avatar
  • 53
1 vote
1 answer
75 views

On the genesis of 'APPROX-QCIRCUIT-PROB': a (promise) BQP-complete problem

Wikipedia mentions APPROX-QCIRCUIT-PROB (AQP) as a (promise) BQP-complete problem. It seems convincing that it is a complete problem for BQP. The lecture notes of Prof. Henry Yuen mention it too, here....
Manish Kumar's user avatar