1
$\begingroup$

From what I know, a problem $p_0$ is BQP-complete if you can reduce any BQP problem $p$ to $p_0$.

There will be an overhead involved in doing the reduction from $p$ to $p_0$. What I was wondering was the following. Is the overhead in going from $p$ to $p_0$ classically polynomial or quantum polynomial?

If it were quantum polynomial, then surely any BQP problem would be a BQP-complete problem.

Could someone point me to a rigorous definition of a BQP-complete problem and what the overhead involved is?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ See here: quantumcomputing.stackexchange.com/q/31705/9474 $\endgroup$
    – Egretta.Thula
    Jun 27 at 18:03
  • $\begingroup$ How does "if it were quantum polynomial, then surely any BQP problem would be a BQP-complete problem" follow? Factoring is not likely to be (promise) BQP-complete, but any reduction that uses Factoring likely wouldn't be in P either. $\endgroup$
    – Mark Spinelli
    Jun 27 at 20:20
  • $\begingroup$ wouldn’t *necessarily be in P (sorry). $\endgroup$
    – Mark Spinelli
    Jun 28 at 0:56
  • $\begingroup$ @MarkSpinelli I've had a look at that post and thanks for your interesting answer, which from what I've gathered, is dependent on O'Donnel's claim. I was wondering if you managed to pin down this elusive proof. I thought it would follow in the following way: you could simply reduce any BQP problem to the empty problem quantum-polynomially by definition. $\endgroup$
    – Sean Thrasher
    Jun 28 at 14:43
  • $\begingroup$ I haven’t yet found the proofs mentioned by O’Donnell, but I haven’t really looked tbqh. Also, I always forget which way the reduction goes! For example do we reduce problems to Hamiltonian simulation, or the other way around? I can never remember. $\endgroup$
    – Mark Spinelli
    Jun 29 at 0:17

1 Answer 1

Reset to default
1
$\begingroup$

A problem is (Promise)-BQP complete if:

  1. The problem is in Promise-BQP, and
  2. The problem is Promise-BQP hard.

In general the reduction in (2) often uses Feynman-Kitaev clocks and looks very similar to those in Feynman's original outline showing Hamiltonian simulation is Promise-BQP hard, as discussed by @DaftWullie here.

For example, one fun Promise-BQP problem of Janzing and Wocjan involves estimating a number of $m$-length classical discrete-time random walks along an implicitly defined large graph that start and end at the same home position. But, the proof of the Promise-BQP Completeness in their paper is fundamentally a quantum reduction and looks strikingly similar to the granddaddy problem of Hamiltonian simulation. That is, after showing that their problem is in BQP through careful control of various errors in their algorithm, the authors go on to reduce Hamiltonian simulation to the problem of estimating the diagonal entries in a large matrix. Figure 1 in their paper used in the reduction, is certainly quantum.

Indeed I can imagine a hypothetical reduction from a problem $p$ to a problem $p_0$ that has a subroutine involving factoring large numbers a polynomial number of times. Certainly using factoring, which is not known to be classically polynomial but is in BQP, does not preclude the problem so reduced that just uses factoring as a subroutine from being Promise-BQP complete (although factoring itself is not likely to be BQP complete).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer. Aren't conditions two and one the same thing? $\endgroup$
    – Sean Thrasher
    Jun 28 at 22:03
  • $\begingroup$ Indeed no. For example, a problem that is QMA-complete (I think) must be BQP-hard, and isn’t in BQP unless BQP=QMA. Similarly, some problems are NP-hard but are not likely to actually be in NP, as they might require superpolynomial certificate. $\endgroup$
    – Mark Spinelli
    Jun 28 at 22:22
  • $\begingroup$ The Venn diagram on NP-completeness on Wikipedia is very good. A problem that’s hard for one class may include problems that aren’t even in that class. $\endgroup$
    – Mark Spinelli
    Jun 29 at 0:19

Your Answer

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

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