An official website of the United States government
The calculation of off-diagonal matrix elements has various applications in fields such as nuclear physics and quantum chemistry. In this paper, we present a noisy intermediate scale quantum algorithm for estimating the diagonal and off-diagonal matrix elements of a generic observable in the energy eigenbasis of a given Hamiltonian without explicitly preparing its eigenstates. By means of numerical simulations we show that this approach finds many of the matrix elements for the one and two qubits cases. Specifically, while in the first case, one can initialize the ansatz parameters over a broad interval, in the latter the optimization landscape can significantly slow down the speed of convergence and one should therefore be careful to restrict the initialization to a smaller range of parameters.
more »
« less
High Order Coherence Functions and Spectral Distributions as Given by the Scully-Lamb Quantum Theory of the Laser
We propose and demonstrate a method for measuring the time evolution of the off-diagonal elements ρ n,n + k ( t ) of the reduced density matrix obtained from the quantum theory of the laser. The decay rates of the off-diagonal matrix element ρ n,n + k ( t ) (k = 2,3) are measured for the first time and compared with that of ρ n,n +1 ( t ), which corresponds to the linewidth of the laser. The experimental results agree with the Scully-Lamb quantum theory of the laser.
more »
« less
- Award ID(s):
- 2013771
- PAR ID:
- 10284474
- Date Published:
- Journal Name:
- Frontiers in Physics
- Volume:
- 9
- ISSN:
- 2296-424X
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In the light bulb problem, one is given uniformly random vectors x1,…,xn,y1,…,yn∈{−1,1}d. They are all chosen independently except a planted pair (xi∗,yj∗) is chosen with correlation ρ>0. The goal is to find the planted pair. This problem was introduced over 30 years ago by L.~Valiant, and is known to have many applications in data analysis, statistics, and learning theory. The naive algorithm runs in Ω(n2) time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as ρ→0. In 2012, G.~Valiant gave a breakthrough algorithm using fast matrix multiplication that runs in time O(n(5−ω)/(4−ω))0 is. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to O(n2ω/3)0. We also introduce a new tensor T2112, which has the same size of 2×2 matrix multiplication tensor, but runs faster than the Strassen's algorithm for light bulb problem.more » « less
-
null (Ed.)The distance matrix $$\mathcal{D}(G)$$ of a graph $$G$$ is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is $$\mathcal{D}^L (G)=T(G)-\mathcal{D} (G)$$, where $T(G)$ is the diagonal matrix of row sums of $$\mathcal{D}(G)$$. Several general methods are established for producing $$\mathcal{D}^L$$-cospectral graphs that can be used to construct infinite families. Examples are provided to show that various properties are not preserved by $$\mathcal{D}^L$$-cospectrality, including examples of $$\mathcal{D}^L$$-cospectral strongly regular and circulant graphs. It is established that the absolute values of coefficients of the distance Laplacian characteristic polynomial are decreasing, i.e., $$|\delta^L_{1}|\geq \cdots \geq |\delta^L_{n}|$$, where $$\delta^L_{k}$$ is the coefficient of $x^k$.more » « less
-
We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an n × n matrix A, accessible only though matrix-vector products with A and AT. We prove that, for the rank-k HODLR approximation problem, our method achieves a (1 + β )log(n )-optimal approximation in expected Frobenius norm using O (k log(n )/β3) matrix-vector products. In particular, the algorithm obtains a (1 + ∈ )-optimal approximation with O (k log4(n )/∈3) matrix-vector products, and for any constant c, an nc-optimal approximation with O (k log(n )) matrix-vector products. Apart from matrix-vector products, the additional computational cost of our method is just O (n poly(log(n ), k, β )). We complement the upper bound with a lower bound, which shows that any matrix-vector query algorithm requires at least Ω(k log(n ) + k/ε ) queries to obtain a (1 + ε )-optimal approximation. Our algorithm can be viewed as a robust version of widely used “peeling” methods for recovering HODLR matrices and is, to the best of our knowledge, the first matrix-vector query algorithm to enjoy theoretical worst- case guarantees for approximation by any hierarchical matrix class. To control the propagation of error between levels of hierarchical approximation, we introduce a new perturbation bound for low-rank approximation, which shows that the widely used Generalized Nyström method enjoys inherent stability when implemented with noisy matrix-vector products. We also introduce a novel randomly perforated matrix sketching method to further control the error in the peeling algorithm.more » « less
-
We prove lower bounds on the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Using a novel way of applying recording query methods we show that for many linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices A, including the discrete Fourier transform (DFT) matrix, we prove that quantum circuits with at most T input queries and S qubits of memory require T=Ω(n^2/S) to compute matrix-vector product Ax for x ∈ {0,1}^n. We similarly prove that matrix multiplication for nxn binary matrices requires T=Ω(n^3/√S). Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems at any space bound. We also improve the previous quantum time-space tradeoff lower bounds for n× n Boolean (i.e. AND-OR) matrix multiplication from T=Ω(n^2.5/S^0.5) to T=Ω(n^2.5/S^0.25) which has optimal exponents for the powerful query algorithms to which it applies. Our method also yields improved lower bounds for classical algorithms.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3389/fphy.2021.657333
