Timeline for Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 6, 2023 at 18:01 | history | edited | Discrete lizard | CC BY-SA 4.0 | added 1 character in body |
| Jul 6, 2023 at 17:45 | review | Suggested edits | |||
| S Jul 6, 2023 at 18:01 | |||||
| Jun 19, 2018 at 18:21 | comment | added | Discrete lizard | @JanVdA I answered only what I think is the main question here, which concerns all possible quantum algorithms. If you're interested in common aspects of existing algorithms, it might be better to ask a separate question about that specifically. | |
| Jun 19, 2018 at 12:47 | comment | added | JanVdA | I understand that from a theoretical point of view we can not make such a general statement but what about a practical point of view. We have the quantum zoo listing a whole set of quantum algorithms providing a speed up compared to the classical algorithm. For me it would be interesting to understand the common aspects of those algorithms that resulted in the speedup compared to classical algorithms. | |
| Apr 5, 2018 at 7:37 | comment | added | Niel de Beaudrap | I took your mention of "the quantum gate model" as an invitation to consider theoretical models of quantum computation, in which we list allowed operations. PostBQP is the class arising if you suppose that postselection is an allowed operation which has only constant cost. Of course, we can accommodate postselection just by making it part of the conditions we want on the measured output. But we can do the same for classical computation, and no-one seriously suggests that postselection is a technique for efficient classical computation (you can 'solve' NP-complete problems that way). | |
| Apr 5, 2018 at 7:13 | comment | added | Discrete lizard | @NieldeBeaudrap I'm not sure what you mean by 'model' here. If we say that we have some circuit and perform postselection afterwards. This may be inefficient, but it is possible. But perhaps PostBQP really is too far from the practical machines that it shouldn't be considered at all. I'll have a look at ZQP, that might indeed be relevant. | |
| Apr 4, 2018 at 21:34 | comment | added | Niel de Beaudrap | Can we really say that PostBQP comes anywhere close to problems which are efficiently solvable by quantum computers (in any model)? Your own remarks about practically implementing postselection would suggest not, and postselection is certainly not allowed in the definition of the unitary circuit model. Would not ZQP be a much better candidate (more restrictive than BQP in that it would in principle never produce an erroneous result, and of non-trivial interest because it contains integer factorisation)? | |
| Apr 4, 2018 at 7:58 | comment | added | Mithrandir24601♦ | There are, um, interesting uses for small numbers of qubits, but as far as I'm aware, there aren't any practical and scalable implementations, no | |
| Apr 4, 2018 at 7:55 | history | edited | Discrete lizard | CC BY-SA 3.0 | add clarification on postselection |
| Apr 4, 2018 at 7:54 | comment | added | Discrete lizard | @Mithrandir24601 So, there are no practical implementations of postselection. | |
| Apr 4, 2018 at 7:50 | comment | added | Mithrandir24601♦ | Postselection can be achieved with a quantum processor that doesn't use postselection using classical post-processing. The issue is that it generally requires an exponential number of runs | |
| Apr 4, 2018 at 7:39 | history | answered | Discrete lizard | CC BY-SA 3.0 |