# On the paper "Quantum Computing Hamiltonian cycles"

The paper Quantum Computing Hamiltonian cycles 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 on bipartite ∩ maximum degree 3 graphs hamiltonian cycle is NP-complete.

cstheory claims

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.

• 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.) Jun 22, 2020 at 12:34
• @EmilJeřábek Unless it is collision of names, the author appears highly cited on scholar.google.com: scholar.google.com/…
– joro
Jun 22, 2020 at 13:12
• 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". Jun 22, 2020 at 13:16
• @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. Jun 22, 2020 at 13:30
• @smapers The paper is indeed wrong, check my answer.
– joro
Jun 23, 2020 at 17:14