Skip to main content
deleted 1249 characters in body
Source Link
Mark Spinelli
  • 14.4k
  • 3
  • 24
  • 78

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...


The early history of the definition of BQP is pretty fascinating. Much as physicists in the 60's and 70's had fun quantizing various fields while they built the Standard Model, around '85 or so and following Feynman with a suggestion from Bennett, Deutsch similarly quantized Turing machines. Later in the early 90's under the suggestion of Goldschlager, Bernstein and Vazirani defined BQP based on these Turing machines while Yao rewrote the language in terms of gates (again with both Feynman and Deutsch having some earlier precedents). The gate-based definition of BQP lacked the now-standard uniformity condition; this was also fixed early enough (I think by Solovay, or maybe Shor himself?)

Even QMA has also had an interesting history of getting the definition "just right". I have heard that, while on an airplane for a conference on quantum computing sometime in the late 90's, Kitaev worked on a presentation, roughly defining NQP and proving that the local Hamiltonian problem is NQP-complete, by strong analogy to the Cook-Levin proof; concurrently Watrous had shown that Group Non-Membership, as an oracle problem, is in QMA. People realized that Kitaev's NQP was the same as Watrous's QMA, so now we speak of Kitaev's proof of the QMA-completeness of the local Hamiltonian problem.


Although it would be ideal towe could prove that problems are BQP- or QMA- or QCMA-complete by a reduction to the (quantum) Turing-machine model, nobody does this any moreafter 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.

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...


The early history of the definition of BQP is pretty fascinating. Much as physicists in the 60's and 70's had fun quantizing various fields while they built the Standard Model, around '85 or so and following Feynman with a suggestion from Bennett, Deutsch similarly quantized Turing machines. Later in the early 90's under the suggestion of Goldschlager, Bernstein and Vazirani defined BQP based on these Turing machines while Yao rewrote the language in terms of gates (again with both Feynman and Deutsch having some earlier precedents). The gate-based definition of BQP lacked the now-standard uniformity condition; this was also fixed early enough (I think by Solovay, or maybe Shor himself?)

Even QMA has also had an interesting history of getting the definition "just right". I have heard that, while on an airplane for a conference on quantum computing sometime in the late 90's, Kitaev worked on a presentation, roughly defining NQP and proving that the local Hamiltonian problem is NQP-complete, by strong analogy to the Cook-Levin proof; concurrently Watrous had shown that Group Non-Membership, as an oracle problem, is in QMA. People realized that Kitaev's NQP was the same as Watrous's QMA, so now we speak of Kitaev's proof of the QMA-completeness of the local Hamiltonian problem.


Although it would be ideal to prove that problems are BQP- or QMA- or QCMA-complete by a reduction to the (quantum) Turing-machine model, nobody does this any more because quantum Turing machines are so darn difficult to work with. So mostly it's just done relative to the gate model  ...

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.

Source Link
Mark Spinelli
  • 14.4k
  • 3
  • 24
  • 78

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...


The early history of the definition of BQP is pretty fascinating. Much as physicists in the 60's and 70's had fun quantizing various fields while they built the Standard Model, around '85 or so and following Feynman with a suggestion from Bennett, Deutsch similarly quantized Turing machines. Later in the early 90's under the suggestion of Goldschlager, Bernstein and Vazirani defined BQP based on these Turing machines while Yao rewrote the language in terms of gates (again with both Feynman and Deutsch having some earlier precedents). The gate-based definition of BQP lacked the now-standard uniformity condition; this was also fixed early enough (I think by Solovay, or maybe Shor himself?)

Even QMA has also had an interesting history of getting the definition "just right". I have heard that, while on an airplane for a conference on quantum computing sometime in the late 90's, Kitaev worked on a presentation, roughly defining NQP and proving that the local Hamiltonian problem is NQP-complete, by strong analogy to the Cook-Levin proof; concurrently Watrous had shown that Group Non-Membership, as an oracle problem, is in QMA. People realized that Kitaev's NQP was the same as Watrous's QMA, so now we speak of Kitaev's proof of the QMA-completeness of the local Hamiltonian problem.


Although it would be ideal to prove that problems are BQP- or QMA- or QCMA-complete by a reduction to the (quantum) Turing-machine model, nobody does this any more because quantum Turing machines are so darn difficult to work with. So mostly it's just done relative to the gate model ...