Can we convert every algorithm in $\text{P}$ (polynomial time complexity for deterministic machines) into a quantum algorithm with polynomial time and $O(\log n)$ quantum bit?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ You would have to specify how you provide the input (which could be poly-sized), as well as (in the circuit model) the way in which you create the quantum circuit for a given input size. $\endgroup$– Norbert SchuchOct 21, 2018 at 21:26
-
1$\begingroup$ @NorbertSchuch: There is a standard solution to the input specification question in sub-linear-space complexity, which is to suppose that the input is provided in a Read-Only manner (similarly, to suppose that the output can only be performed in a Write-Once manner), and to only count the amount of rewritable workspace. However, the question of how the circuit is to be generated is a crucial one for this question: its not at all clear how it could be done unitarily (and the most obvious approach to doing so would not only be non-unitary, but also non-linear). $\endgroup$– Niel de BeaudrapOct 21, 2018 at 22:19
-
2$\begingroup$ @NieldeBeaudrap Is it evident how to provide a read-only classical input to a quantum computer? Would you use an oracle? (I mean, you can't just dispose of qubits - unless you allow for CP maps or the like.) --- I'm confused by the second part of your comment: Shouldn't the circuit be generated by a classical Turing machine, whose power possibly has to be carefully assessed in this case? --- In any case, the problem is probably more well-defined with a quantum turing machine. $\endgroup$– Norbert SchuchOct 22, 2018 at 7:54
-
$\begingroup$ @NorbertSchuch I think the classical definition could be extended here. we can use three quantum tape that the first is read only and saves the input. the second one is working quantum tape with $O(\log n)$ QBITS and the third is another quantum tape for outputs and we don't need the classical one in this definition. $\endgroup$– Mohsen GhorbaniOct 22, 2018 at 8:40
-
1$\begingroup$ @NorbertSchuh: (i) We can consider unitary circuits generated by logspace-TMs; there are no known instances where this would significantly restrict the circuits that could be generated, related to the fact that we do not know how to prove P≠L. (ii) You could describe access to the input as 'oracle access'. A more transparent (but equivalent) description would be 'classical control', i.e. you allow the input to control gates in the circuit, to the point of reading some of the input bits into your quantum state if you so wish. (iii) There is almost never a good reason to use QTMs. $\endgroup$– Niel de BeaudrapOct 22, 2018 at 9:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
It seems this problem is open.
Watrous [J. Comp. Sys. Sci. 59, (pp. 281-326), 1999] proved that any space $s$ bounded quantum Turing Machine (for space constructible $s(n)>\Omega(\log n)$) can be simulated by deterministic Turing machine with $O(s^2)$ space. With the assumption $\mathsf{P \neq SC}$ (where $\mathsf{SC \subseteq P}$ is defined as the class of problems solvable by a DTM simultaneously in polynomial time and poly-logarithmic space), quantum machines will not reduce space complexity exponentially.
N.B. We don't know whether $\mathsf{P=SC}$ or not, though it is considered unlikely that they would be equal.
-
2$\begingroup$ Good thinking to look up John Watrous' work on space complexity, I think you've got the complete picture here (or as complete a picture as is available at the moment, in any case). $\endgroup$ Oct 23, 2018 at 9:20
-
1$\begingroup$ You should accept your own answer, by the way! $\endgroup$ Oct 24, 2018 at 22:11