<p><em><strong>Summary.</em></strong> All of these papers misunderstand the notion of quantum superpositions and interference, and lead to analyses which do not conserve probability (<em>i.e.</em>&nbsp;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 <em>post-selection</em> &mdash; 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 <a href="http://en.wikipedia.org/wiki/PostBQP">PostBQP</a>. 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.</p>

<p><em><strong>Details.</em></strong> I've added some elaboration on the failures of the analyses of these articles.</p>

<ol>
<li><p>The article by Shiekh <strong>[cs/0507003]</strong> describes "adding quantum interference to quantum computers". This ignores the fact that:</p>

<ul>
<li>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 <em>avoid</em> exhibiting it); and</li>
<li>The way that quantum interference works is not how Shiekh describes it (in particular, his analysis seems to ignore normalization of probabilities). <br><br>Shiekh supposes that if you have a superposition such as |000&rang;&nbsp;+&nbsp;|001&rang;&nbsp;+&nbsp;...&nbsp;+&nbsp;|111&rang;, that you can simply make a "second copy" of that superposition with some phases (<em>e.g.</em>&nbsp;on the standard basis states which are not satisfying solutions to a SAT formula), obtaining a superposition such as &minus;|000&rang;&nbsp;+&nbsp;|001&rang;&nbsp;&minus;&nbsp;...&nbsp;&minus;&nbsp;|111&rang;, and somehow interfere them to obtain a state of the form |001&rang;, cancelling all of the terms with opposing signs. <br><br> But note that the two superpositions described above are not normalized: this is already a warning sign &mdash; the cancellation should at best yield |001&rang;/2<sup>1&minus;n/2</sup> if you keep track of the normalization, and allow this alternative "interference" process. That's a probability of 1/2<sup>n&minus;2</sup> 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, <em>e.g.</em>&nbsp;a&nbsp;detector, which you should be accounting for).<br><br></li>
</ul></li>
<li><p>The <a href="http://www.du.edu/media/documents/nsm/mathematics/preprints/m0604.pdf">article by Gudder</a> (which you link to in the comments) describes a "quantum wave divider" D<sub><strong>p</strong></sub> (in the words of Long's article, see below) which, for a probability distribution <strong>p</strong>&nbsp;=&nbsp;(<em>p</em><sub>1</sub>&nbsp;,&nbsp;...&nbsp;,&nbsp;<em>p<sub>n</sub></em>), 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 <strong>p</strong> by the Euclidean unit-norm vector <strong>q</strong>&nbsp;=&nbsp;<strong>p</strong>&nbsp;/&nbsp;||<strong>p</strong>||. This "wave splitter" prepares an independent quantum register <em>Q</em> in a state |<strong>q</strong>&rang; which is a superposition over |1&rang;&nbsp;,&nbsp;...&nbsp;,&nbsp;|<em>n</em>&rang;, with coefficients given by <em>q<sub>k</sub></em>&nbsp;=&nbsp;<strong>e<sub><em>k</em></sub></strong><sup>&dagger;</sup>&nbsp;<strong>q</strong>, which is therefore in a tensor product with an input state |&psi;&rang;. So it's no wonder that D<sub><strong>p</strong></sub> so described is an isometry. 
The adjoint "wave combiner" operation, C<sub><strong>p</strong></sub>&nbsp;=&nbsp;D<sub><strong>p</strong></sub><sup>&dagger;</sup> effectively describes the effect of trying to project that register <em>Q</em> back onto the state |<strong>q</strong>&rang;. So of course it will be isometric on the image of D<sub><strong>p</strong></sub>&nbsp;; but unless <em>Q</em> is in the state |<strong>q</strong>&rang;, this operation is norm-decreasing, and therefore is not probability-conserving. Everyting in that article is fine until he proposes to apply C<sub><strong>p</strong></sub>&nbsp;; for instance, the block-diagonal unitary operators are perfectly good <em>coherently-controlled</em> unitary operators conditioned on the register <em>Q</em>.<br><br>
Unfortunately, the operation C<sub><strong>p</strong></sub> which Gudder <em>actually</em> describes is not the adjoint of D<sub><strong>p</strong></sub> &mdash; although he does claim that it is &mdash; but is the adjoint of |1&rang;&nbsp;+&nbsp;...&nbsp;+&nbsp;|<em>n</em>&rang;, 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 D<sub><strong>p</strong></sub> 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&nbsp;2.2, is equal to |&psi;&rang; if and only if <strong>p</strong> is a point-mass function. This result is fact <em>super</em>-normalized: it enables events with probability <em>greater</em> than 1. It's not clear what this would mean; and Gudder proposes no such meaning.<br><br>
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 <strong>[quant-ph/0605087]</strong> (which however does not address the problems with failure to preserve probability, or of what the actual adjoint of D<sub><strong>p</strong></sub> is).<br></p></li>
</ol>

<p>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 <em>not</em> being conserved), and whether the algebra is otherwise sound.</p>

CC BY-SA 3.0
2011-04-13T17:06:01.860Z
I was inclined to shut this question down, because it verges on being subjective/argumentative. But this answer is very helpful without being subjective.
Suresh Venkat
CC BY-SA 3.0
2011-04-13T17:22:12.900Z
Gudder did not write cs/0507003. He wrote this: http://www.du.edu/media/documents/nsm/mathematics/preprints/m0604.pdf I still don't understand this answer.
Craig Feinstein
CC BY-SA 3.0
2011-04-13T17:33:50.667Z
**(i)** Sorry, I mismatched a name to the article. Corrected.
Niel de Beaudrap
CC BY-SA 3.0
2011-04-13T17:54:51.580Z
@Niel, the Gudder article is written in a more technical language. How does your answer pertain to it?
Craig Feinstein
CC BY-SA 3.0
2011-04-13T19:50:02.963Z
**(ii)** I have now revised and elaborated my response. I hope this clarifies things somewhat.
Niel de Beaudrap
CC BY-SA 3.0
2011-04-13T16:36:36.297Z
2011-04-14T06:30:53.037Z
2011-04-14T06:30:53.037Z
Niel de Beaudrap
<p>There is a lot on the internet about quantum computers and how they could factor integers. </p>

<p>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 <a href="http://arxiv.org/abs/cs/0507003" rel="nofollow">http://arxiv.org/abs/cs/0507003</a> and <a href="http://arxiv.org/abs/quant-ph/0605087" rel="nofollow">http://arxiv.org/abs/quant-ph/0605087</a>. These computers have been called "Duality computers".</p>

<p>Why isn't more written about these types of computers? </p>

CC BY-SA 3.0
2011-04-13T16:37:34.323Z
Please explain the model briefly.
Raphael
<quantum-computing>
Duality computers
Craig Feinstein
# Duality computers

(Asked by: username_0 on 2011-04-13)

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?

**Tags:** quantum-computing
> **Comments:**
> **username_1**: Please explain the model briefly.  

---

## 1 answers

### Answer by username_2 on 2011-04-13. Score: 15 | Accepted answer

***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](http://en.wikipedia.org/wiki/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](http://www.du.edu/media/documents/nsm/mathematics/preprints/m0604.pdf) (which you link to in the comments) describes a "quantum wave divider" D**p** (in the words of Long's article, see below) which, for a probability distribution **p** = (*p*1 , ... , *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* = **e*k***† **q**, which is therefore in a tensor product with an input state |ψ⟩. So it's no wonder that D**p** so described is an isometry.
   The adjoint "wave combiner" operation, C**p** = D**p**† 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 D**p** ; 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 C**p** ; for instance, the block-diagonal unitary operators are perfectly good *coherently-controlled* unitary operators conditioned on the register *Q*.  
     
   Unfortunately, the operation C**p** which Gudder *actually* describes is not the adjoint of D**p** — 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 D**p** 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 D**p** 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.

> **Comments:**
> **username_3**: I was inclined to shut this question down, because it verges on being subjective/argumentative. But this answer is very helpful without being subjective.  
> **username_0**: Gudder did not write cs/0507003. He wrote this: http://www.du.edu/media/documents/nsm/mathematics/preprints/m0604.pdf I still don't understand this answer.  
> **username_2**: **(i)** Sorry, I mismatched a name to the article. Corrected.  
> **username_0**: @Niel, the Gudder article is written in a more technical language. How does your answer pertain to it?  
> **username_2**: **(ii)** I have now revised and elaborated my response. I hope this clarifies things somewhat.  

---

