5
$\begingroup$

I'm trying to figure out what is the computational complexity of initializing a quantum register of N qubits.

For my research, I have used the initialize method of qiskit, in which you set the amplitudes of the 2^N basis states to get the desired quantum state. The point is that I can't find a reference that discusses the cost of such an operation. Moreover, if we consider a standard Grover's algorithm, why the initialization of a uniform superposition of basis states is not counted in the complexity?

Improve this question
$\endgroup$
2
  • $\begingroup$ Beware that the initialize method probably simply initializes the simulator with the statevector you give it. I doubt it implements the requisite circuit at all, and you shouldn't rely upon it when developing an algorithm for use in quantum hardware. $\endgroup$
    – jecado
    Commented Oct 8, 2021 at 17:47
  • 1
    $\begingroup$ @jecado the initialize method can be decomposed, although it is a non-unitary Instruction since it contains resets at the beginning, but these can be removed when sending the circuit to a real device since anyways the initial state of the hardware is the ground state. But yes, there are definitely more efficient methods depending on the exact algorithm they are developing. $\endgroup$
    – epelaez
    Commented Oct 9, 2021 at 7:23

2 Answers 2

Reset to default
7
$\begingroup$

The running time of creating any fully separable pure initial state is $O(1)$. This includes the standard $|0\rangle^{\otimes n}$ or something like $|+\rangle^{\otimes n}$, which is the uniform superposition of all basis states. That's because this is just single-qubit preparation performed in parallel.

Improve this answer
$\endgroup$
5
$\begingroup$

For general initial states, i.e., not fully separable, the paper Synthesis of Quantum Logic Circuits gives the Quantum Shannon Decomposition (QSD) algorithm that has a gate count of $\frac{23}{48}4^n-\frac{3}{2}2^n+\frac{4}{3}$ where $n$ is the number of qubits (look at table 1 of the linked paper).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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