4
$\begingroup$

Suppose I have a quantum algorithm that produces solutions where more than one different linear combination of qubit values with raised probability amplitudes is a correct result. Each linear combination is correct in the context of this hypothetical algorithm, but it is not the task of the algorithm to also iteratively elicit the solutions, but merely to produce a superposition where all possible solutions are represented within it. The problem isn't with the implementation of the supposed algorithm, but with the issue of potentially measuring a superposition that hasn't been fully honed to a single maximal linear combination, since in the ensemble of measurements you might obtain each of the different linear combinations, making the results unclear, despite the fact the algorithm implementation is potentially correct. The objective is therefore to have an abstract procedure to read off these possible answers in a clean manner, so that they aren't lost, but for which the superposition has been narrowed to a final value.

For example, suppose I have linear combinations $|10\rangle$ and $|11\rangle$, each which cannot be decomposed into simpler expressions with independent amplitudes, that have raised probability in that, for my quantum algorithm, these are correct. The others, $|00\rangle$ and $|01\rangle$ have amplitudes near zero. For simplicity, it can be said that each the current superposition is described by: $\frac{1}{\sqrt{2}}(|10\rangle + |11\rangle)$. Before reading each value off, I want to cancel the probability of all others aside from the ith term of the superposition. Therefore, first cancel out $|11\rangle$, so that I don't have a very high chance of reading $|11\rangle$ when the first measurement is done, so the superposition becomes simply $|10\rangle$. In every iteration of this procedure, I want the superposition narrowed to a single term, so that there is no confusion upon measurement. As with the example, after the first measurement, repeat, but with probability canceled from $|10\rangle$ to $|11\rangle$.

But, I want a mechanism to do this form me for $N$ possible admissible answers, so that it works in the more general case.

$\endgroup$
  • 1
    $\begingroup$ Could you be more explicit with your example? I’m struggling to understand what you’re asking, particularly the “group the probability” bit. $\endgroup$ – DaftWullie Dec 18 '18 at 6:49
  • $\begingroup$ Alright, I made an edit. Please re-read the question. $\endgroup$ – Adam Miller Dec 22 '18 at 5:08
  • $\begingroup$ By group the probability, I only mean, cancel out the probability of a given term in a superposition, and move the amplitude to a target term. $\endgroup$ – Adam Miller Dec 22 '18 at 5:33
  • $\begingroup$ @AdamMiller Hi, and welcome to Quantum Computing! Please edit to use MathJax to typeset your mathematical expressions from next time onwards. I have done it this time. $\endgroup$ – Sanchayan Dutta Dec 22 '18 at 11:48
2
$\begingroup$

There are a couple of possible strategies that I can think of. I have no idea what their scaling is like. I guess nothing will perform better than random sampling, but that’s a complete guess.

The method I’d start from is just do the usual search, get a random answer, and then adapt my search the next time round, explicitly unmarking that known marked item.

Another option is to use the fact that Grover’s search can be applied to learning the minimum of a set, see What applications does Grover's Search Algorithm have?. So, you might adapt it to find the smallest, then the second smallest, and so on.

$\endgroup$

Your Answer

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

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