Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. The qbits are finally measured; the probability of getting a given state $|b_1,b_2,...,b_n>$ is $P(b_1,b_2,...,b_n)$.

Now, we have an algorithm A that simulates the outcome of the above-described process. It takes an input $\Phi$ (calculated from $C$ by means of an algorithm that runs for whatever finite time) and outputs values of bits $b_1,b_2,...,b_n$ with the above-mentioned probabilities $P(b_1,b_2,...,b_n)$, by using a random number generator. Here, I assume that the results obtained with floating point calculations can be made precise enough by using a long enough sequence of digits, with fixed length, although this could not work in some cases.

My question addresses the size of $\Phi$, depending on the time needed by the algorithm A to run. Here is what I already know.

  1. We can put in $\Phi$ a representation of $C$. This $\Phi$ has polynomial length in $n$. An algorithm A of course exists, it is just a simple quantum calculation. This algorithm A is able to solve APPROX-QCIRCUIT-PROB, which is BQP-complete. It is believed that BQP strictly includes P, thus it is unlikely that such an algorithm A can run in polynomial time in $n$ and probably it will require exponential time.

  2. An algorithm A, running in polynomial time in $n$, can be built, if the probabilities $P$ of all the states $b_1,b_2,...,b_n$ are calculated and written inside $\Phi$. Although a bit tricky, a proper structure can be used to store the states and their probabilities, so that an algorithm A can operate in polynomial time in $n$. This $\Phi$ has exponential size in $n$.

Now, my question is if it possible to have an algorithm A and an input $\Phi$, where $\Phi$ has polynomial length in $n$ and A runs in polynomial time in $n$.

It seems to me that it is not straightforward to show that this is not feasible, for the following reason. Imagine that it were possible to find a proof that my question has negative answer. Then it would be valid for the case (1) above. Then it would also prove that P is strictly included in BQP, which is believed to be a difficult-to-prove fact.

On the other hand, there is an encouraging fact. We know that BQP is included in PSPACE, basically because the calculation of the probabilities $P$ can be done by means of the Feynman integrals. Using a similar idea, we find a method to calculate $P$ starting from $C$ in polynomial time in $n$. However, I was not able to use this property to devise suitable $\Phi$ and A.

The expected answer is a constructive proof of the required algorithm A or a proof that it does not exist, possibly based on some well known conjecture. But any suggestion is welcome. I did not receive any comment: please let me know if you see any difficulty, or if the question is unclear, or it sounds not interesting. Anything that can help me to understand why I'm not getting any answer is also welcome.



Your Answer

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

Browse other questions tagged or ask your own question.