-8
$\begingroup$

There is a lot on the internet about quantum computers and how they could factor integers.

However, there is a type of computer which also uses the principles of quantum mechanics, which can be used to do much more than this, including solving NP-complete problems in an instant. See http://arxiv.org/abs/cs/0507003 and http://arxiv.org/abs/quant-ph/0605087. These computers have been called "Duality computers".

Why isn't more written about these types of computers?

$\endgroup$
  • 7
    $\begingroup$ Please explain the model briefly. $\endgroup$ – Raphael Apr 13 '11 at 16:37
14
$\begingroup$

Summary. All of these papers misunderstand the notion of quantum superpositions and interference, and lead to analyses which do not conserve probability (i.e. in which the probabilities of outcomes do not add to one) without specifying an interpretation for this fact. This may be considered to correspond to post-selection — conditioning on a particular outcome of a measurement; a subject which has indeed been studied in the context of quantum computing, and which is embodied as the complexity class PostBQP. But mostly, I suppose that these articles are ignored because while they propose to extend quantum computation, they seem to display a lack of awareness of fundamentals of quantum computation.

Details. I've added some elaboration on the failures of the analyses of these articles.

  1. The article by Shiekh [cs/0507003] describes "adding quantum interference to quantum computers". This ignores the fact that:

    • Quantum interference is already a feature of quantum computation (and it is in fact difficult to concieve of how a quantum-mechanical version of computation could avoid exhibiting it); and
    • The way that quantum interference works is not how Shiekh describes it (in particular, his analysis seems to ignore normalization of probabilities).

      Shiekh supposes that if you have a superposition such as |000⟩ + |001⟩ + ... + |111⟩, that you can simply make a "second copy" of that superposition with some phases (e.g. on the standard basis states which are not satisfying solutions to a SAT formula), obtaining a superposition such as −|000⟩ + |001⟩ − ... − |111⟩, and somehow interfere them to obtain a state of the form |001⟩, cancelling all of the terms with opposing signs.

      But note that the two superpositions described above are not normalized: this is already a warning sign — the cancellation should at best yield |001⟩/21−n/2 if you keep track of the normalization, and allow this alternative "interference" process. That's a probability of 1/2n−2 of obtaining the result you want, which is still vanishingly small. But what happens if this result is not realized? Shiekh's analysis doesn't even propose any answer, and so it is incomplete. Worse still, what happens if there are no satisfying solutions at all, and all the terms cancel out? You're left with the zero vector: the system is in no state at all, which could be construed as a contradiction of the concept of "state", unless you propose that the system has been utterly destroyed (which would presumably affect the state of some other system, e.g. a detector, which you should be accounting for).

  2. The article by Gudder (which you link to in the comments) describes a "quantum wave divider" Dp (in the words of Long's article, see below) which, for a probability distribution p = (p1 , ... , pn), performs a mapping $$\begin{align} |\psi\rangle \mapsto \frac{1}{\|\mathbf p\|_2} \bigoplus_{j=1}^n \; p_j |\psi\rangle \;. \end{align}$$ Yes, that's the Euclidean norm in the denominator, which effectively replaces the probability distribution p by the Euclidean unit-norm vector q = p / ||p||. This "wave splitter" prepares an independent quantum register Q in a state |q⟩ which is a superposition over |1⟩ , ... , |n⟩, with coefficients given by qk = ek q, which is therefore in a tensor product with an input state |ψ⟩. So it's no wonder that Dp so described is an isometry. The adjoint "wave combiner" operation, Cp = Dp effectively describes the effect of trying to project that register Q back onto the state |q⟩. So of course it will be isometric on the image of Dp ; but unless Q is in the state |q⟩, this operation is norm-decreasing, and therefore is not probability-conserving. Everyting in that article is fine until he proposes to apply Cp ; for instance, the block-diagonal unitary operators are perfectly good coherently-controlled unitary operators conditioned on the register Q.

    Unfortunately, the operation Cp which Gudder actually describes is not the adjoint of Dp — although he does claim that it is — but is the adjoint of |1⟩ + ... + |n⟩, which is a non-normalized version of the uniform superposition over all computational basis states. One can see that this is not actually the adjoint of Dp by noting that $$\begin{align} C_{\mathbf p} D_{\mathbf p} |\psi\rangle \;=\; C_{\mathbf p} \left[ \frac{1}{\|\mathbf p\|_2} \bigoplus_{j = 1}^n \; p_j |\psi\rangle \right] \;=\; \sum_{j = 1}^n \;\frac{p_j}{\| \mathbf p \|_2} |\psi\rangle \;=\; \left( \sum_{j = 1}^n \; q_j \right) |\psi\rangle \end{align}$$ which, contrary to his claim in Lemma 2.2, is equal to |ψ⟩ if and only if p is a point-mass function. This result is fact super-normalized: it enables events with probability greater than 1. It's not clear what this would mean; and Gudder proposes no such meaning.

    Gudder's article actually has a number of such problems with linear algebra. Some of the mistakes he makes in the context of mixed states are addressed by Long's paper [quant-ph/0605087] (which however does not address the problems with failure to preserve probability, or of what the actual adjoint of Dp is).

So, that's likely why these ideas are not widely studied. Generally, whenever there is an article which claims to generalize quantum computation in some bold new manner, one should check whether probability is conserved (and what significance the authors attribute to it not being conserved), and whether the algebra is otherwise sound.

$\endgroup$
  • 1
    $\begingroup$ I was inclined to shut this question down, because it verges on being subjective/argumentative. But this answer is very helpful without being subjective. $\endgroup$ – Suresh Venkat Apr 13 '11 at 17:06
  • $\begingroup$ Gudder did not write cs/0507003. He wrote this: du.edu/media/documents/nsm/mathematics/preprints/m0604.pdf I still don't understand this answer. $\endgroup$ – Craig Feinstein Apr 13 '11 at 17:22
  • $\begingroup$ (i) Sorry, I mismatched a name to the article. Corrected. $\endgroup$ – Niel de Beaudrap Apr 13 '11 at 17:33
  • $\begingroup$ @Niel, the Gudder article is written in a more technical language. How does your answer pertain to it? $\endgroup$ – Craig Feinstein Apr 13 '11 at 17:54
  • $\begingroup$ (ii) I have now revised and elaborated my response. I hope this clarifies things somewhat. $\endgroup$ – Niel de Beaudrap Apr 13 '11 at 19:50

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.