Assume we are given an $n$-qubit system and complex numbers $a_0, \ldots, a_{m-1}$ with $m = 2^n$. Assume further we start with the initial state $|0 \ldots 0\rangle$ and want to make the transformation $$|0 \ldots 0\rangle \rightarrow \frac{1}{\sqrt{\sum_{i=0}^{m-1} |a_i|^2 }}\sum_{i=0}^{m-1} a_i |i\rangle$$ for arbitrary $a_i$. My question is now: What is the most efficient way (fewest gates resp. smallest circuit depth resp. best robustness on a noisy intermediate-scale quantum computer) currently known to implement that transformation?
4
-
2$\begingroup$ This looks essentially equivalent to the quantum gate-synthesis problem, that is, the problem of decomposing a given unitary using a sequence of gates in a pre-defined gate set (although in principle if the target is only a specific state this might be easier, I don't know). This is an extremely complex problem subject to much research, and the ansewr strongly depends on the specifics of the problem. This is a relatively recent paper on the topic, so you might have a look at the references in the introduction in that paper. $\endgroup$– glS ♦May 27, 2019 at 1:32
-
$\begingroup$ The best pointer here seems to be quantum RAM (QRAM). See e.g. here for some details. $\endgroup$– smapersMay 27, 2019 at 12:41
-
$\begingroup$ @smapers a QRAM is not a quantum circuit though, but rather a scheme to load classical information into a quantum memory. It does not realise a transformation between states like it is asked in the question $\endgroup$– glS ♦May 28, 2019 at 16:11
-
$\begingroup$ You're right. A better pointer would be e.g. here, section 5.1, by Kerenidis and Prakash. Here they effectively propose an architecture to achieve the above transformation. $\endgroup$– smapersMay 29, 2019 at 16:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
For completely arbitrary coefficients you are out of luck. A simple counting argument says that because:
1) The coefficients are continuous parameters 2) gates implement discrete operations $\to$ There is no finite circuit to prepare the vast majority of states. However, if you're okay with an arbitrarily good approximation to your state, then it can be done with relatively short gate sequences by the Solovay–Kitaev theorem. An algorithm for doing this is given here: https://arxiv.org/pdf/quant-ph/0505030
The most efficient is hard to say since, as you point out, there are many different metrics to choose from and this is an intensive area of active research. So I'd say as long as you're not writing quantum compilers and if you want something that will work for completely arbitrary state preparation, then the Solovay–Kitaev algorithm is a solid choice. If you are writing a quantum compiler you'll need to do a months long, intensive literature review.
Here's a recent paper I read that is cutting edge: https://arxiv.org/pdf/1807.03206
IBM's documentation (IBM Arbitrary Initialization) says it uses the techniques from: https://arxiv.org/pdf/quant-ph/0406176.pdf to accomplish this
I'll also give a nod to dissipative state preparation since that's something I personally work on and it seems to have some promise - but it's still too early for it to be really practical.
-
$\begingroup$ Quick note: Solovay-Kitaev algorithm approximates unitary matrices with a very big gate count. Moreover, you will not be able to use it for 3-qubit gates and over (theoretically it works, in practice it requires too much computing power). $\endgroup$ Jun 10, 2019 at 7:29
-
1$\begingroup$ You should expect, for a generic unitary, to need an exponentially large number of elementary gates to approximate it in number of qubits and logarithmically large number in the inverse of the accuracy. So the large gate count from SK is not necessarily indicative of an inefficient algorithm but rather that the problem is hard. If I know ahead of time which transformation I want to approximate, I can often do better but here we seek an algorithm that will work for completely general unitaries $\endgroup$– bRost03Jun 10, 2019 at 12:08
-
1$\begingroup$ I agree, it was just a note to clarify a few things. Your explanation summarize what I wanted to say $\endgroup$ Jun 10, 2019 at 12:25
-
$\begingroup$ The Q# library function PrepareArbitraryState, docs.microsoft.com/qsharp/api/qsharp/…, is also based on the paper by Shende, Bullock, and Markov. You can look at the source code at github.com/microsoft/QuantumLibraries/blob/master/Standard/src/…. $\endgroup$ Jun 10, 2019 at 17:04