Questions tagged [space-complexity]

Space complexity describes the amount of memory space required by a deterministic Turing machine to solve a given computational problem with a certain algorithm. If necessary, also use the [memory-space] tag.

Filter by
Sorted by
Tagged with
1
vote
1answer
77 views

Why does entanglement complicate quantum simulation?

To model a single qubit one would need enough memory for $2$ complex numbers. If we have an $N$ qubit system, we would have to store $2N$ complex numbers. The general statement is that to store an $N$-...
0
votes
1answer
33 views

How many real numbers are required to describe density matrix for $n$ qubits?

(All of these coming from the topic of simulation of quantum systems) A density matrix $\rho$ Which describe state of $n$ qubits will have $2^{n} \times 2^{n}$ size. We have couple of conditions like ...
1
vote
0answers
126 views

What is the cost of implementing the Quantum Fourier transform in a classical computer? [closed]

What is the cost of implementing the Quantum Fourier transform (QFT) in a classical computer? We know we require at least $\log{n}$ depth quantum circuits to do a QFT in a quantum computer, with $n$ ...
2
votes
1answer
335 views

Is there a polynomial quantum algorithm for graph coloring?

Is there a polynomial time and polynomial space quantum algorithm for finding a 4 colouring of any loopless planar graph?
6
votes
1answer
217 views

Can we use quantum machines to reduce space complexity of deterministic turing machines?

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?