arXiv:1902.07890 · Scientific Reports

Finding Hadamard Matrices by a Quantum Annealing Machine

Andriyan Bayu Suksmono, Yuichiro Minato

Published Oct 7, 2019• 7 citations

Abstract

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.

DOI: 10.1038/s41598-019-50473-w

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 ReportsJan 7, 20223 citations

Finding high-order Hadamard matrices by using quantum computers

Andriyan Bayu Suksmono, Yuichiro Minato

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.

arXiv:2009.10919Sep 23, 20201 citation

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.

EntropyFeb 22, 20185 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.07964Scientific ReportsSep 26, 20250 citations

A Survey of Quadratization Methods Used in QUBO Formulations and their Usage in Quantum and Digital Annealing

Geethika Prabhath, Anuradha Mahasinghe, Nalin Ranasinghe +1 more

Quantum annealing is a metaheuristic method aimed at finding the global minimum of a pseudo-Boolean quadratic function. To solve a problem by a quantum annealer, it must be restated as a QUBO (quadratic unconstrained binary optimization) problem, the standard format acceptable to an annealer. However, there are many natural problems that turn out be of cubic or higher order, yet promising solutions can be obtained for many instances using quantum annealers, after converting to the QUBO format, using order reduction criteria. Accordingly, quadratization becomes a crucial preprocessing step in order to make use of present-day quantum annealing hardware that relies on coupling technology, which can only process interactions of at most degree two. A critical challenge is that quadratization methods often require many additional variables, degrading the performance of the annealers. A number of algorithmic and heuristic quadratization techniques have been proposed and used for annealing in the literature, affecting the performance of the annealers differently. We examine a number of such quadratization techniques, focusing on their efficiency, compactness, and applicability. We analyze the approaches motivated by diverse goals and highlight the transition from foundational approaches to more recent compact approaches. An evaluation of the current usage of different quadratization methods in the literature is carried out at the end of the survey. Further, we comment on the limitations on usage and show possible opportunities to enhance the performance of annealers.

Journal of Computer ScienceJan 1, 20260 citations

Optimization with Quantum Annealing Machines

Samuel Deleplanque

Quantum annealing is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.

Jul 3, 20220 citations