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.
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.