Quantum Algorithms from a Linear Algebra Perspective

Eugenia-Maria Kontopoulou, Gregory Dexter, Wojciech Szpankowski A +2 more

, named after John von Neumann, is an extension of the classical concept of entropy to the field of quantum mechanics. From a numerical perspective, von Neumann entropy can be computed simply by computing all eigenvalues of a density matrix, an operation that could be prohibitively expensive for large-scale density matrices. We present and analyze three randomized algorithms to approximate von Neumann entropy of real density matrices: our algorithms leverage recent developments in the Randomized Numerical Linear Algebra (RandNLA) literature, such as randomized trace estimators, provable bounds for the power method, and the use of random projections to approximate the eigenvalues of a matrix. All three algorithms come with provable accuracy guarantees and our experimental evaluations support our theoretical findings showing considerable speedup with small loss in accuracy.

Yunah Choi, Jeihee Cho, Shiho Kim

Thomas Beth, Martin Rötteler

Jincheng Zhang

Quantum-enhanced linear algebra seeks to leverage the unique capabilities of quantum computers to dramatically improve the computational efficiency of linear algebra problems. This paper proposes a novel hybrid quantum-classical algorithm designed to achieve exponential speedups in solving linear systems, addressing a longstanding challenge in numerical linear algebra. We detail the core mechanism of this algorithm, outlining its integration of quantum algorithms for computationally intensive operations and its potential impact across diverse fields. The research highlights a significant departure from traditional approaches, promising a paradigm shift in how linear algebra computations are performed.

I. S. Eliëns, S. G. A. Brito, R. Chaves

Bell's theorem, stating that quantum predictions are incompatible with a local hidden variable description, is a cornerstone of quantum theory and at the center of many quantum information processing protocols.Over the years, different perspectives on nonlocality have been put forward as well as different ways to detect nonlocality and quantify it.Unfortunately, and in spite of its relevance, as the complexity of the Bell scenario increases, deciding whether a given observed correlation is nonlocal becomes computationally intractable.Here, we propose to analyze a Bell scenario as a tensor network, a perspective permitting us to test and quantify nonlocality, resorting to very efficient algorithms originating from compressed sensing and that offer a significant speedup in comparison with standard linear programming methods.We use that all nonsignaling correlations can be described by hidden variable models governed by a quasiprobability, a fact we prove with simple linear algebra methods.

Peter Høyer