5
$\begingroup$

I have recently worked on a problem involving a rather large Hamiltonian, which I wrote some Python code for its generation following the method in this paper.
No when I used qiskits to_circuit_op() method for decomposing the operator into a circuit, my runtime went through the roof for larger qubit numbers.

While for my particular problem there are easy workarounds, I am a bit curious on what the runtime complexity of such a decomposition algorithm is. Surely if it were exponential, this would be a big problem for quantum simulation algorithms, since we always will have to decompose into some set of gates if we want to run it on an actual physical quantum computer?

Improve this question
$\endgroup$
7
  • $\begingroup$ arxiv.org/abs/2106.05305 seems related $\endgroup$
    – glS ♦
    Commented Apr 16, 2023 at 14:09
  • 3
    $\begingroup$ @glS not quite. Anyhow, the question is kind of ill-posed. If the input is an exponentially-size matrix, then it is clear that any algorithm needs at least exponential time. A more interesting question is if we have an efficient description, e.g. a sparse/local Hamiltonian, a constant-size quantum circuit, or similar, can we do better? qiskit apparently can't, but TBH that's not surprising. Importantly, many interesting problems have an efficient description to start with. $\endgroup$
    – Markus Heinrich
    Commented Apr 17, 2023 at 7:31
  • 1
    $\begingroup$ I think you are misunderstanding my question. I am asking about the complexity of the decomposition from a unitary operator, which may represent such an efficient Hamiltonian, into a quantum circuit that implements it. $\endgroup$
    – greilchri
    Commented Apr 17, 2023 at 8:10
  • $\begingroup$ Are you saying that you are asking about circuit complexity? Perhaps you should clarify this. $\endgroup$
    – Markus Heinrich
    Commented Apr 17, 2023 at 9:39
  • $\begingroup$ I will try to give a example of what I mean. Lets say we have a Hamiltonian Ĥ for a n-qubit system. Lets assume we derived as in the paper I linked, so it will be a series of unitary operations. Of course, the matrix representation will be 2^n, but clearly we are not interested in that. Instead, if we want to implement it on a QC for lets say, VQE, we will need the circuit representation. But the calculation of what the circuit looks like is also exponential in n, there would be no speedup over just taking the matrix representation and solving the eigenvalue problem on it, in my understanding $\endgroup$
    – greilchri
    Commented Apr 17, 2023 at 10:03

0

Reset to default