Skip to main content
edited body
Source Link
Mark Spinelli
  • 14.4k
  • 2
  • 24
  • 78

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~20~30 years.

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~20 years.

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~30 years.

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

Oracle separations and black-box separations are effectively synonymous.

Simon didn't give any specific language $L$ that can be solved more efficiently on a quantum computer than on a classical computer, because he did not, in particular, instantiate his this by applying it to a language that satisfies his promise. Rather, he gave a class of languages $O$, and showed that, relative to this class, $\mathsf{BPP}^O\ne\mathsf{BQP}^O$.

We say "in the black-box setting, a quantum computer needs fewer oracle calls than a classical computer to solve an instance of Simon's problem." We don't yet have a particular instance of a language that is in Simon's class of languages - that satisfies Simon's promise -because we don't know how to instantiate it concretely, even after ~20 years.