Yusaku YAMAMOTO (山本 有作)

ABSTRACT

Approximate block diagonalization is a problem of transforming a given symmetric matrix as close to block diagonal as possible by symmetric permutations of its rows and columns. This problem arises as a preprocessing stage of various scientific calculations and has been shown to be NP‐complete. In this paper, we consider solving this problem approximately using the D‐Wave Advantage quantum annealer. For this purpose, several steps are needed. First, we have to reformulate the problem as a quadratic unconstrained binary optimization (QUBO) problem. Second, the QUBO has to be embedded into the physical qubit network of the quantum annealer. Third, and optionally, reverse annealing for improving the solution can be applied. We propose two QUBO formulations and four embedding strategies for the problem and discuss their advantages and disadvantages. Through numerical experiments, it is shown that the combination of domain‐wall encoding and D‐Wave's automatic embedding is the most efficient in terms of usage of physical qubits, while the combination of one‐hot encoding and automatic embedding is superior in terms of the probability of obtaining a feasible solution. It is also shown that reverse annealing is effective in improving the solution for medium‐sized problems.

Abstract

The generalized Newton shift is a generalization of the Newton shift for computing the singular values of a bidiagonal matrix with the dqds or mdLVs algorithm and is defined as $$\left( \textrm{Tr}\left( \left( B^{(n)}\right) ^{\top } B^{(n)}\right) ^{-p}\right) ^{-1/p}$$ , where $$B^{(n)}$$ is the bidiagonal matrix at the n-th iteration and p is some positive integer. This quantity can be computed in O(pm) work, where m is the order of the matrix, and another $$O(p^2 m)$$ subtraction-free algorithm is also available for higher accuracy. We analyze the asymptotic convergence property of the dqds algorithm with the generalized Newton shift and show that its order of convergence is $$p+1-\epsilon $$ for any $$\epsilon >0$$ . This result is confirmed by numerical experiments. Since the generalized Newton shift can achieve arbitrarily high order of convergence, it should be useful as a building block for constructing an efficient shifting strategy for the dqds algorithm.

Abstract

The famous Toda equation is an integrable system related to similarity transformations of tridiagonal matrices. The discrete Toda equation, which is a time-discretization of the Toda equation, is essentially the recursion formula of the quotient-difference (qd) algorithm for computing eigenvalues of tridiagonal matrices. Another time-discretization of the Toda equation is the $q$-discrete Toda equation, which is derived by replacing standard derivatives with the so-called $q$-derivatives that involves a parameter $q$ such that $0<q<1$. In a prior work, we related the $q$-discrete Toda equation to implicit-shift $LR$ transformations (which are similarity transformations) of tridiagonal matrices. Furthermore, we developed the determinantal solution to clarify the convergence as discrete-time goes to infinity. In this paper, we propose an extension of the $q$-discrete Toda equation as a time-discretization of the Kostant–Toda equation and then show the convergence as discrete-time goes to infinity from the perspective of implicit-shift $LR$ transformations of Hessenberg matrices. We also present numerical examples to verify the convergence as discrete-time goes to infinity in the proposed $q$-discrete Kostant–Toda equation.