1
$\begingroup$

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.

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

1 Answer 1

Reset to default
4
$\begingroup$

I emailed the author.

He replied "yes that paper is wrong!".

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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