6
$\begingroup$

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?

$\endgroup$
  • 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 Schuch Oct 21 '18 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 Beaudrap Oct 21 '18 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 Schuch Oct 22 '18 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 Ghorbani Oct 22 '18 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 Beaudrap Oct 22 '18 at 9:37
4
$\begingroup$

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.

$\endgroup$
  • 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$ – Niel de Beaudrap Oct 23 '18 at 9:20
  • 1
    $\begingroup$ You should accept your own answer, by the way! $\endgroup$ – Niel de Beaudrap Oct 24 '18 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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