  Solving hard problems is one of the most important issues in computing to be
addressed by a quantum computer. Previously, we have shown that the H-SEARCH;
which is the problem of finding a Hadamard matrix (H-matrix) among all possible
binary matrices of corresponding order, is a hard problem that can be solved by
a quantum computer. However, due to the limitation on the number of qubits and
connections in present day quantum processors, only low orders H-SEARCH are
implementable. In this paper, we show that by adopting classical
construction/search techniques of the H-matrix, we can develop new quantum
computing methods to find higher order H-matrices. Especially, the Turyn-based
quantum computing method can be further developed to find an arbitrarily high
order H-matrix by balancing the classical and quantum resources. This method is
potentially capable to find some unknown H-matrices of practical and scientific
interests, where a classical computer alone cannot do because of the
exponential grow of the complexity. We present some results of finding H-matrix
of order more than one hundred and a prototypical experiment to find even
higher order matrix by using the classical-quantum resource balancing method.
Although heuristic optimizations generally only achieve approximate solutions,
whereas the exact one should be determined by exhaustive listing; which is
difficult to perform, in the H-SEARCH we can assure such exactness in
polynomial time by checking the orthogonality of the solution. Since quantum
advantage over the classical computing should have been measured by comparing
the performance in solving a problem up to a definitive solution, the proposed
method may lead to an alternate route for demonstrating practical quantum
supremacy in the near future.
