You are given a quantum state$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$ $\ket\psi$ with $2n$ qubits and the possibility to recreate the state $m$ times, but only one at a time. Further $m$ grows polynomial with $n$, i.e. $m=O(poly(n))$. Your task is to determine the probability (or even harder the coefficient) of $\ket{00\cdots0}$ in $\ket\psi$, so you start to measure.

Since you don't have enough (exponentially many) copies to fully characterize $\ket\psi$, what is the best strategy to at least get an upper bound on the probability to measure $\ket{00\cdots 0}$?

Is brute force measuring the best or could entanglement help?


Ok, so what one can do is to measure all qubits and collapse the state to $\ket{ m_0m_1\cdots m_{2n-1}}$, where $m_k$ is the measured $k$-th qubit $\in \{\ket0,\ket1\}$. And then I count ($\#C_{\ket{00\cdots 0}}$) how many $\ket{00\cdots 0}$ I had and divide by $m$. This gives at least the probability $\displaystyle p_{\ket{00\cdots 0}}=\frac{\#C_{\ket{00\cdots 0}}}{m}$.

But doesn't measuring any $\ket0$ at any qubit $k$ (I assume that qubits are measured one by one) and statistics on that affect my overall $p_{\ket{00\cdots 0}}$?


I thought of some statistical thing like Bayesian Inference, testing of hypothesis,.... Can these methods be applied?

E.g. if I only look at the first measured qubit. If I measure a $\ket0$, the worst (for my prediction) that can happen is that the other two remaining qubits are in a equal superposition, so the best guess I can make is $\#C_{\ket{0}}/4m$...

  • $\begingroup$ You may have underconstrained your problem. Given the loose constraints of your problem, I doubt you have any chance of being lucky or having entanglement help. For example you could set up $m$ copies of a solution to a satisfiability problem. Knowing the amplitude of $\vert 00\cdots 0\rangle$ with only $m$ queries may correspond to knowing a solution to the satisfiability problem in linear time. $\endgroup$
    – Mark S
    May 4 '20 at 20:48
  • $\begingroup$ Could quantum tomography help? $\endgroup$ May 4 '20 at 21:23
  • $\begingroup$ @MarkS that's why I ask for an optimal way to get the best upper bound for the real value $\endgroup$
    – draks ...
    May 5 '20 at 6:52
  • 1
    $\begingroup$ @MartinVesely do we have enough copies for that? BTW : using entanglement is not preferred $\endgroup$
    – draks ...
    May 5 '20 at 6:56
  • $\begingroup$ You’re asking for the amplitude/probability of a specific vector. Wlog your state could be any basis vector. I’m not sure what you mean by using entanglement. You’re unlikely to get better than running some Feynman path integral to find the amplitude of your state. $\endgroup$
    – Mark S
    May 5 '20 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.