<p>I emailed the author.</p>
<p>He replied &quot;yes that paper is wrong!&quot;.</p>
<p>He has lost the passwords to remove it from the web.</p>

CC BY-SA 4.0
2020-06-23T16:45:29.437Z
2020-06-23T16:45:29.437Z
joro
<p>The paper <a href="http://arxiv.org/pdf/quant-ph/9603001v1.pdf" rel="nofollow noreferrer">Quantum Computing Hamiltonian cycles</a> claims:</p>
<blockquote>
<p>An algorithm for quantum computing Hamiltonian cycles of simple,
cubic, bipartite graphs is discussed. It is shown that it is possible to
evolve a quantum computer into an entanglement of states which map
onto the set of all possible paths initiating from a chosen vertex, and
furthermore to subsequently project out all states not corresponding to
Hamiltonian cycles.</p>
</blockquote>
<p>The algorithm requires polynomial in <span class="math-container">$n$</span> qubits and gives
example with a quantum &quot;gadget&quot;.</p>
<p>According to <a href="https://graphclasses.org/classes/gc_941.html" rel="nofollow noreferrer">graphclasses</a>
on bipartite ∩ maximum degree 3 graphs hamiltonian cycle is NP-complete.</p>
<p><a href="https://cstheory.stackexchange.com/questions/6000/hard-problems-on-subclasses-of-planar-cubic-bipartite-graphs/6012#6012">cstheory claims</a></p>
<blockquote>
<p>Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem</p>
</blockquote>
<p>Since cubic planar bipartite graphs are subset of cubic bipartite
graphs, hamiltonicity of cubic bipartite graphs must be NP-hard too.</p>
<p>Doesn't the above arguments show that quantum computer can solve
NP-complete problem, including SAT, which appears to be open problem?</p>
<p>Can the paper be extended to other subclasses of graphs for which
hamiltonicity is NP-hard?</p>
<p>Bugs me the date of the paper is 29th February 1995 and this date
doesn't exist, since odd year can't be leap year.</p>

CC BY-SA 4.0
2020-06-22T12:34:38.600Z
Is there any evidence that the paper is credible? It does not seem to have been published. (NB: The date is obviously hardcoded in the paper. You can put anything you want in the \date{} field. The date generated by default by LaTeX also does not have a "th" and a period at the end. The paper was actually submitted to arXiv on 3 March **1996**.)
Emil Jeřábek
CC BY-SA 4.0
2020-06-22T13:12:39.900Z
@EmilJeřábek Unless it is collision of names, the author appears highly cited on scholar.google.com:  https://scholar.google.com/citations?user=Y8cRR70AAAAJ&hl=bg&oi=sra
joro
CC BY-SA 4.0
2020-06-22T13:16:46.287Z
The catch is that "projecting out the states" that do not correspond to Hamiltonian cycles cannot be done efficiently in general. In fact, it's almost like saying "pick a random path, and post-select on that path being a Hamiltonian cycle".
smapers
CC BY-SA 4.0
2020-06-22T13:30:41.293Z
@joro Even the best researchers can make mistakes. Unless I missed something, *this particular* paper has no citations according to Google scholar, and does not appear to have been published in any peer-reviewed venue. Those are red flags. But I won’t speculate any further as I know next to nothing about quantum computing.
Emil Jeřábek
CC BY-SA 4.0
2020-06-23T17:14:28.767Z
@smapers The paper is indeed wrong, check my answer.
joro
<graph-theory><np-hardness><quantum-computing><hamiltonian-paths>
On the paper "Quantum Computing Hamiltonian cycles"
joro
# On the paper "Quantum Computing Hamiltonian cycles"

(Asked by: username_0 on 2020-06-22)

The paper [Quantum Computing Hamiltonian cycles](http://arxiv.org/pdf/quant-ph/9603001v1.pdf) claims:

> An algorithm for quantum computing Hamiltonian cycles of simple,
> cubic, bipartite graphs is discussed. It is shown that it is possible to
> evolve a quantum computer into an entanglement of states which map
> onto the set of all possible paths initiating from a chosen vertex, and
> furthermore to subsequently project out all states not corresponding to
> Hamiltonian cycles.

The algorithm requires polynomial in $n$ qubits and gives
example with a quantum "gadget".

According to [graphclasses](https://graphclasses.org/classes/gc_941.html)
on bipartite ∩ maximum degree 3 graphs hamiltonian cycle is NP-complete.

[cstheory claims](https://cstheory.stackexchange.com/questions/6000/hard-problems-on-subclasses-of-planar-cubic-bipartite-graphs/6012#6012)

> Several hard graph problems remain hard on planar cubic bipartite graphs. They include Hamiltonian cycle problem

Since cubic planar bipartite graphs are subset of cubic bipartite
graphs, hamiltonicity of cubic bipartite graphs must be NP-hard too.

Doesn't the above arguments show that quantum computer can solve
NP-complete problem, including SAT, which appears to be open problem?

Can the paper be extended to other subclasses of graphs for which
hamiltonicity is NP-hard?

Bugs me the date of the paper is 29th February 1995 and this date
doesn't exist, since odd year can't be leap year.

**Tags:** graph-theory, np-hardness, quantum-computing, hamiltonian-paths

> **Comments:**
> **username_1**: Is there any evidence that the paper is credible? It does not seem to have been published. (NB: The date is obviously hardcoded in the paper. You can put anything you want in the \date{} field. The date generated by default by LaTeX also does not have a "th" and a period at the end. The paper was actually submitted to arXiv on 3 March **1996**.)  
> **username_0**: @EmilJeřábek Unless it is collision of names, the author appears highly cited on scholar.google.com:  https://scholar.google.com/citations?user=Y8cRR70AAAAJ&hl=bg&oi=sra  
> **username_2**: The catch is that "projecting out the states" that do not correspond to Hamiltonian cycles cannot be done efficiently in general. In fact, it's almost like saying "pick a random path, and post-select on that path being a Hamiltonian cycle".  
> **username_1**: @username_0 Even the best researchers can make mistakes. Unless I missed something, *this particular* paper has no citations according to Google scholar, and does not appear to have been published in any peer-reviewed venue. Those are red flags. But I won’t speculate any further as I know next to nothing about quantum computing.  
> **username_0**: @username_2 The paper is indeed wrong, check my answer.  

---

## 1 answers

### Answer by username_0 on 2020-06-23. Score: 4 | Accepted answer

I emailed the author.

He replied "yes that paper is wrong!".

He has lost the passwords to remove it from the web.


---

