Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2009.10919

Finding high-order Hadamard matrices by using quantum computers

Andriyan Bayu Suksmono, Yuichiro Minato

Published Sep 23, 2020• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2009.10919

Related papers

Quantum computing formulation of some classical Hadamard matrix searching methods and its implementation on a quantum computer

Andriyan Bayu Suksmono, Yuichiro Minato

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.

Scientific Reports•Jan 7, 2022•3 citations

Finding Hadamard Matrices by a Quantum Annealing Machine

Andriyan Bayu Suksmono, Yuichiro Minato

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.

arXiv:1902.07890•Scientific Reports•Oct 7, 2019•7 citations

A quantum approximate optimization method for finding Hadamard matrices

Andriyan Bayu Suksmono

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.

arXiv:2408.07964•Scientific Reports•Sep 26, 2025•0 citations

Finding a Hadamard Matrix by Simulated Quantum Annealing

Andriyan Bayu Suksmono

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.

Entropy•Feb 22, 2018•5 citations

QW-HHL: A Quantum Computer Amenable General Matrix Equation Solver

Christopher D. Phillips, Helia Akbari, Vladimir Okhmatovski

Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.

IEEE journal on multiscale and multiphysics computational techniques•Jan 1, 2026•1 citation

Quantum Algorithms and Hard Problems

C. Vidya Raj, H. D. Phaneendra, M. S. Shivakumar

Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer

IEEE International Conference on Cognitive Informatics•Jul 1, 2006•5 citations
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.
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.
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.
Quantum computation offers a promising alternative to classical computing methods in many areas of numerical science, with algorithms that make use of the unique ways in which quantum computers store and manipulate data often achieving dramatic improvements in performance over their classical counterparts. The potential efficiency of quantum computers is particularly important for numerical simulations, where the capabilities of classical computing systems are often insufficient for the analysis of real-world problems. In this work, we study problems involving the solution of matrix equations, for which there is limited research on efficient, general, and fully implemented quantum procedures. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary, which we have adopted from research in the area of quantum walks, has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware for any well-conditioned system. The procedure is most useful for sparse matrix equations, as it allows for the inverse of a matrix to be applied with O(sN log(N)) complexity, where N is the number of unknowns, and s is an upper bound on the number of nonzero elements in any row of the system matrix. This efficiency is competitive with the most sophisticated available classical solvers, and is independent of the structure of the input matrix. Hence, this procedure represents an important step towards the achievement of quantum advantage over classical algorithms for practical problems in numerical science.
Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer