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. Due to the limitation on the number of qubits and connections in current quantum processors, only low order H-matrix search of orders 2 and 4 were implementable by previous method. In this paper, we show that by adopting classical searching techniques of the H-matrices, we can formulate new quantum computing methods for finding higher order ones. We present some results of finding H-matrices of order up to more than one hundred and a prototypical experiment of the classical-quantum resource balancing method that yields a 92-order H-matrix previously found by Jet Propulsion Laboratory researchers in 1961 using a mainframe computer. Since the exactness of the solutions can be verified by an orthogonality test performed in polynomial time; which is untypical for optimization of hard problems, the proposed method can potentially be used for demonstrating practical quantum supremacy in the near future.
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. Due to the limitation on the number of qubits and connections in current quantum processors, only low order H-matrix search of orders 2 and 4 were implementable by previous method. In this paper, we show that by adopting classical searching techniques of the H-matrices, we can formulate new quantum computing methods for finding higher order ones. We present some results of finding H-matrices of order up to more than one hundred and a prototypical experiment of the classical-quantum resource balancing method that yields a 92-order H-matrix previously found by Jet Propulsion Laboratory researchers in 1961 using a mainframe computer. Since the exactness of the solutions can be verified by an orthogonality test performed in polynomial time; which is untypical for optimization of hard problems, the proposed method can potentially be used for demonstrating practical quantum supremacy in the near future.
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.
Abstract Finding a Hadamard matrix (H-matrix) among the set of all binary matrices of corresponding order is a hard problem, which potentially can be solved by quantum computing. We propose a method to formulate the Hamiltonian of finding H-matrix problem and address its implementation limitation on existing quantum annealing machine (QAM) that allows up to quadratic terms, whereas the problem naturally introduces higher order ones. For an M-order H-matrix, such a limitation increases the number of variables from M2 to (M3 + M2 − M)/2, which makes the formulation of the Hamiltonian too exhaustive to do by hand. We use symbolic computing techniques to manage this problem. Three related cases are discussed: (1) finding N < M orthogonal binary vectors, (2) finding M-orthogonal binary vectors, which is equivalent to finding a H-matrix, and (3) finding N-deleted vectors of an M-order H-matrix. Solutions of the problems by a 2-body simulated annealing software and by an actual quantum annealing hardware are also discussed.
Finding a Hadamard matrix of a specific order using a quantum computer can lead to a demonstration of practical quantum advantage. Earlier efforts using a quantum annealer were impeded by the limitations of the present quantum resource and its capability to implement high order interaction terms, which for an M-order matrix will grow by [Formula: see text]. In this paper, we propose a novel qubit-efficient method by implementing the Hadamard matrix searching algorithm on a gate-based quantum computer. We achieve this by employing the Quantum Approximate Optimization Algorithm (QAOA). Since high order interaction terms that are implemented on a gate-based quantum computer do not need ancillary qubits, the proposed method reduces the required number of qubits into O(M). We present the formulation of the method, construction of corresponding quantum circuits, and experiment results in both a quantum simulator and a real gate-based quantum computer.
Hard problems have recently become an important issue in computing. Various methods, including a heuristic approach that is inspired by physical phenomena, are being explored. In this paper, we propose the use of simulated quantum annealing (SQA) to find a Hadamard matrix, which is itself a hard problem. We reformulate the problem as an energy minimization of spin vectors connected by a complete graph. The computation is conducted based on a path-integral Monte-Carlo (PIMC) SQA of the spin vector system, with an applied transverse magnetic field whose strength is decreased over time. In the numerical experiments, the proposed method is employed to find low-order Hadamard matrices, including the ones that cannot be constructed trivially by the Sylvester method. The scaling property of the method and the measurement of residual energy after a sufficiently large number of iterations show that SQA outperforms simulated annealing (SA) in solving this hard problem.
Classical computing there are multiple algorithms to efficiently locate a certain element within a disorganized database; however, quantum computing can be applied more assertively in the face of problems in which it is complicated to verify a solution and at the same time to test multiple and possible solutions. Therefore, this article presents an introduction to Quantum Computing, developing some concepts of quantum formalism, and then approach Grover's algorithm which exploits the principle of superposition to the maximum. Finally, a classic simulation of this algorithm is performed, and the results obtained are compared with classical algorithms such as sequential search and binary search method. A 95% is obtained as a result of greater effectiveness in times -when solving the same search-, revealing the potential advantages of quantum computing.
Quantum computers open up new possibilities for faster and more efficient solutions to real-world, large-scale optimization problems that currently pose a challenge for classical computer systems. One such problem is searching very large neighborhoods, with an exponential number of elements, in local search algorithms for solving NP-hard problems. Currently, the only barrier to the effective use of quantum computers in optimization is the limited number of available qubits. Therefore, the main challenge today, given the limited number of qubits, is to formulate the problem to be solved in a form that minimizes the number of variables and, consequently, the number of necessary qubits. To meet these expectations, we propose a new solution representation used to generate neighborhoods with an exponential number of elements. We prove that for n -element permutations, the number of elements in this neighborhood is the n -th Fibonacci number. Permutations are commonly represented by binary matrices with n2 elements. We propose a new, cost-effective method for representing solutions using n−1 element binary sequences. For an n=50 element permutation, the former requires 2500 qubits, while the latter requires only 49. Computational experiments for a certain NP-hard single-machine scheduling problem were performed on a D-Wave quantum computer. The obtained results clearly indicate the high effectiveness of the presented method. With a limited number of qubits, it is possible to search neighborhoods for much larger permutations. By examining the capabilities and limitations of current quantum annealers, we can more precisely identify them and then use them in the construction of new algorithms better suited to current and future quantum computers.