1
$\begingroup$

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.

It seems inspired by a classical BPP-complete problem called the Circuit Approximation Probability Problem. (see mathoverflow post)

I found no citation in the Wikipedia page for its source/author.

I would like to know the original paper from which this is taken. Or, at least, some paper where this is formally discussed.

Another related query is:

Is there some justification for using the word 'APPROX' in the name?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Interesting question. Perhaps it’s a folk result from when people started thinking about these things? Or maybe when Yao proved the circuit-to-Turing machine equivalence? It’s a pretty natural decision problem I think… $\endgroup$
    – Mark Spinelli
    Commented Apr 27 at 11:51
  • $\begingroup$ @MarkSpinelli, Thanks! I am inspecting Yao paper for the same reason. $\endgroup$
    – Manish Kumar
    Commented Apr 27 at 11:56
  • $\begingroup$ I have added a sub-question just now. I find it quite related to it. Let me know if a separate question on it is essential. $\endgroup$
    – Manish Kumar
    Commented May 2 at 17:00
  • $\begingroup$ @MarkSpinelli : maybe there is something strange in the Wikipedia definition. It requires that the number of gates m is polynomial in the number of qubits n. But n and m are inputs to the problem! This strange thing does not appear in the linked paper. Can you confirm that Wikipedia is wrong? $\endgroup$
    – Doriano Brogioli
    Commented Sep 9 at 8:56
  • 1
    $\begingroup$ No, I think Wikipedia is correct on this point. Otherwise what else would you mean when you say that the complexity grows polynomially with $n$? That said, there are interesting issues about the requirements for uniformity in relating (Turing) machines with a potentially infinite tape to finite-sized (quantum) circuits, and also about, e.g., translationally invariant Hamiltonians. If you are able formulate and post a particular question, I and/or others might be able to answer. $\endgroup$
    – Mark Spinelli
    Commented Sep 9 at 12:28

1 Answer 1

Reset to default
1
$\begingroup$

I do think it's kind of implicit in Yao's Quantum Circuit Complexity, especially in the proof of Theorem 1 of that paper; otherwise I think it's a bit of a folk-theorem. Yao speaks of the standard promise gap of $1/3$ vs. $2/3$ for one single qubit in the output, the same as the Wiki article on the AQP problem.

Being (promise) BQP-complete means both being in (promise) BQP and being BQP-hard.

Although we could prove that problems are BQP- or QMA- or QCMA-complete by a reduction to the (quantum) Turing-machine model, nobody does this after Yao because quantum Turing machines are so darn difficult to work with. So mostly it's just done relative to the gate model... that is how, e.g., the Jones polynomial proof goes through most days.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the answer. $\endgroup$
    – Manish Kumar
    Commented May 2 at 16:52
  • $\begingroup$ I have just added a sub-question as follows: ''Is there some justification for using the word 'APPROX' in the name?'' I find it quite related to it. Kindly let me know if a separate question on it would be more helpful. $\endgroup$
    – Manish Kumar
    Commented May 2 at 16:54
  • 1
    $\begingroup$ Actually I guess we are trying to approximate the average value of the first qubit, up to an error of $\alpha-\beta$. This makes my other answer in your similar question slightly wrong too. $\endgroup$
    – Mark Spinelli
    Commented May 2 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.