Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA QUBO Algorithm to Compute Eigenvectors of Symmetric Matrices
103
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We describe an algorithm to compute the extremal eigenvalues and corresponding eigenvectors of a symmetric matrix by solving a sequence of Quadratic Binary Optimization problems. This algorithm is robust across many different classes of symmetric matrices, can compute the eigenvector/eigenvalue pair to essentially arbitrary precision, and with minor modifications can also solve the generalized eigenvalue problem. Performance is analyzed on small random matrices and selected larger matrices from practical applications.
rate research
Read More
Quantum walks are widely and successfully used to model diverse physical processes. This leads to computation of the models, to explore their properties. Quantum walks have also been shown to be universal for quantum computing. This is a more subtle result than is often appreciated, since it applies to computations run on qubit-based quantum computers in the single walker case, and physical quantum walks in the multi-walker case (quantum cellular automata). Nonetheless, quantum walks are powerful tools for quantum computing when correctly applied. In this paper, I explain the relationship between quantum walks as models and quantum walks as computational tools, and give some examples of their application in both contexts.
We describe an explicit algorithm to factorize an even antisymmetric N^2 matrix into triangular and trivial factors. This allows for a straight forward computation of Pfaffians (including their signs) at the cost of N^3/3 flops.
We investigate eigenvectors of rank-one deformations of random matrices $boldsymbol B = boldsymbol A + theta boldsymbol {uu}^*$ in which $boldsymbol A in mathbb R^{N times N}$ is a Wigner real symmetric random matrix, $theta in mathbb R^+$, and $boldsymbol u$ is uniformly distributed on the unit sphere. It is well known that for $theta > 1$ the eigenvector associated with the largest eigenvalue of $boldsymbol B$ closely estimates $boldsymbol u$ asymptotically, while for $theta < 1$ the eigenvectors of $boldsymbol B$ are uninformative about $boldsymbol u$. We examine $mathcal O(frac{1}{N})$ correlation of eigenvectors with $boldsymbol u$ before phase transition and show that eigenvectors with larger eigenvalue exhibit stronger alignment with deforming vector through an explicit inverse law. This distribution function will be shown to be the ordinary generating function of Chebyshev polynomials of second kind. These polynomials form an orthogonal set with respect to the semicircle weighting function. This law is an increasing function in the support of semicircle law for eigenvalues $(-2: ,+2)$. Therefore, most of energy of the unknown deforming vector is concentrated in a $cN$-dimensional ($c<1$) known subspace of $boldsymbol B$. We use a combinatorial approach to prove the result.
We prove localization with high probability on sets of size of order $N/log N$ for the eigenvectors of non-Hermitian finitely banded $Ntimes N$ Toeplitz matrices $P_N$ subject to small random perturbations, in a very general setting. As perturbation we consider $Ntimes N$ random matrices with independent entries of zero mean, finite moments, and which satisfy an appropriate anti-concentration bound. We show via a Grushin problem that an eigenvector for a given eigenvalue $z$ is well approximated by a random linear combination of the singular vectors of $P_N-z$ corresponding to its small singular values. We prove precise probabilistic bounds on the local distribution of the eigenvalues of the perturbed matrix and provide a detailed analysis of the singular vectors to conclude the localization result.
We propose a new algorithm to compute the X-ray transform of an image represented by unit (pixel/voxel) basis functions. The fundamental issue is equivalently calculating the intersection lengths of the ray with associated units. For any given ray, we first derive the sufficient and necessary condition for non-vanishing intersectability. By this condition, we then distinguish the units that produce valid intersections with the ray. Only for those units rather than all the individuals, we calculate the intersection lengths by the obtained analytic formula. The proposed algorithm is adapted to 2D/3D parallel beam and 2D fan beam. Particularly, we derive the transformation formulas and generalize the algorithm to 3D circular and helical cone beams. Moreover, we discuss the intrinsic ambiguities of the problem itself, and present a solution. The algorithm not only possesses the adaptability with regard to the center position, scale and size of the image, but also is suited to parallelize with optimality. The comparison study demonstrates the proposed algorithm is fast, more complete, and is more flexible with respect to different scanning geometries and different basis functions. Finally, we validate the correctness of the algorithm by the aforementioned scanning geometries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
