1,720,982 research outputs found
The role of encodings and distance metrics for the quantum nearest neighbor
No full textOver the past few years, we observed a rethinking of classical artificial intelligence algorithms from a quantum computing perspective. This trend is driven by the peculiar properties of quantum mechanics, which offer the potential to enhance artificial intelligence capabilities, enabling it to surpass the constraints of classical computing. However, redesigning classical algorithms into their quantum equivalents is not straightforward and poses numerous challenges. In this study, we analyze in-depth two orthogonal designs of the quantum K-nearest neighbor classifier. In particular, we show two solutions based on amplitude encoding and basis encoding of data, respectively. These two types of encoding impact the overall structure of the respective algorithms, which employ different distance metrics and show different performances. By breaking down each quantum algorithm, we clarify and compare implementation aspects ranging from data preparation to classification. Eventually, we discuss the difficulties associated with data preparation, the theoretical advantage of quantum algorithms, and their impact on performance with respect to the classical counterpart
Counting Fiedler pencils with repetitions
Get PDFWe introduce a new notation based on diagrams to deal with Fiedler pencils with repetitions (FPR), and use it to solve several counting problems. In particular, we give explicit recurrences to count the number of FPRs of a given degree d, the number of symmetric, palindromic and antipalindromic ones (where the latter two structures are intended in the sense of [5]). We relate these structures to the presence of symmetries in the associated diagrams
Quantum clustering with k-Means: A hybrid approach
No full textQuantum computing, based on quantum theory, holds great promise as an advanced computational paradigm for achieving fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degrees of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms are theoretically faster than the classical algorithm, while experiments suggest that it is possible to obtain comparable clustering results
When is a matrix unitary or Hermitian plus low rank?
Get PDFHermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low-rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low-rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low-rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew-Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low-rank perturbation. Numerical tests prove that this straightforward algorithm is effective
Recommended from our members
Estimating an Eigenvector by the Power Method with a Random Start
Get PDFThis paper addresses the problem of approximating an eigenvector belonging to the largest eigenvalue of a symmetric positive definite matrix by the power method. We assume that the starting vector is randomly chosen with uniform distribution over the unit sphere. This paper provides lower and upper as well as asymptotic bounds on the randomized error in the Lp sense, p ∈[1,+ ∞]. We prove that it is impossible to achieve sharp bounds that are independent of the ratio between the two largest eigenvalues. This should be contrasted to the problem of approximating the largest eigenvalue, for which Kuczyński and Woźniakowski [SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1094--1122] proved that it is possible to bound the randomized error at the kth step with a quantity that depends only on k and on the size of the matrix. We prove that the rate of convergence depends on the ratio of the two largest eigenvalues, on their multiplicities, and on the particular norm. The rate of convergence is at most linear in the ratio of the two largest eigenvalues
Fast QR iterations for unitary plus low rank matrices
Get PDFSome fast algorithms for computing the eigenvalues of a block companion matrix A=U+XYH, where U∈Cn×n is unitary block circulant and X,Y∈Cn×k, have recently appeared in the literature. Most of these algorithms rely on the decomposition of A as product of scalar companion matrices which turns into a factored representation of the Hessenberg reduction of A. In this paper we generalize the approach to encompass Hessenberg matrices of the form A=U+XYH where U is a general unitary matrix. A remarkable case is U unitary diagonal which makes possible to deal with interpolation techniques for rootfinding problems and nonlinear eigenvalue problems. Our extension exploits the properties of a larger matrix A^ obtained by a certain embedding of the Hessenberg reduction of A suitable to maintain its structural properties. We show that A^ can be factored as product of lower and upper unitary Hessenberg matrices possibly perturbed in the first k rows, and, moreover, such a data-sparse representation is well suited for the design of fast eigensolvers based on the QR/QZ iteration. The resulting algorithm is fast and backward stable
Effect of Different Encodings and Distance Functions on Quantum Instance-based Classifiers
No full textEffects of Different Encodings and Distance Functions on Quantum Instance-based Classifiers
No full textWe illustrate and compare alternatives for the quantum nearest neighbour classifier focus- ing on data preparation and performance. We discuss the differences in the classification process depending on data encoding, storage, and distance functions. The results show that the quantum nearest neighbour approach compares well with the classic version
- …
