Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum-classical algorithms for skewed linear systems with optimized Hadamard test
68
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The solving of linear systems provides a rich area to investigate the use of nearer-term, noisy, intermediate-scale quantum computers. In this work, we discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases. Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth and the number of circuits is much smaller than their Hilbert space dimension. Our algorithms have poly-logarithmic dependence on the dimension and polynomial dependence in other natural quantities. In addition, we present an algorithm for the special case of a factorized linear system with run time poly-logarithmic in the respective dimensions. At the core of these algorithms is the Hadamard test and in the second part of this paper we consider the optimization of the circuit depth of this test. Given an $n$-qubit and $d$-depth quantum circuit $mathcal{C}$, we can approximate $langle 0|mathcal{C}|0rangle$ using $(n + s)$ qubits and $Oleft(log s + dlog (n/s) + dright)$-depth quantum circuits, where $sleq n$. In comparison, the standard implementation requires $n+1$ qubits and $O(dn)$ depth. Lattice geometries underlie recent quantum supremacy experiments with superconducting devices. We also optimize the Hadamard test for an $(l_1times l_2)$ lattice with $l_1 times l_2 = n$, and can approximate $langle 0|mathcal{C} |0rangle$ with $(n + 1)$ qubits and $Oleft(d left(l_1 + l_2right)right)$-depth circuits. In comparison, the standard depth is $Oleft(d n^2right)$ in this setting. Both of our optimization methods are asymptotically tight in the case of one-depth quantum circuits $mathcal{C}$.
rate research
Read More
In order to support near-term applications of quantum computing, a new compute paradigm has emerged--the quantum-classical cloud--in which quantum computers (QPUs) work in tandem with classical computers (CPUs) via a shared cloud infrastructure. In this work, we enumerate the architectural requirements of a quantum-classical cloud platform, and present a framework for benchmarking its runtime performance. In addition, we walk through two platform-level enhancements, parametric compilation and active qubit reset, that specifically optimize a quantum-classical architecture to support variational hybrid algorithms (VHAs), the most promising applications of near-term quantum hardware. Finally, we show that integrating these two features into the Rigetti Quantum Cloud Services (QCS) platform results in considerable improvements to the latencies that govern algorithm runtime.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $Ax = b$, we show that there is a classical algorithm that outputs a data structure for $x$ allowing sampling and querying to the entries, where $x$ is such that $|x - A^{-1}b|leq epsilon |A^{-1}b|$. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $widetilde{O}(kappa_F^6 kappa^2/epsilon^2 )$, where $kappa_F = |A|_F|A^{-1}|$ and $kappa = |A||A^{-1}|$. This improves the previous best algorithm [Gily{e}n, Song and Tang, arXiv:2009.07268] of complexity $widetilde{O}(kappa_F^6 kappa^6/epsilon^4)$. Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when $A$ is row sparse, this method already returns an approximate solution $x$ in time $widetilde{O}(kappa_F^2)$, while the best quantum algorithm known returns $ket{x}$ in time $widetilde{O}(kappa_F)$ when $A$ is stored in the QRAM data structure. As a result, assuming access to QRAM and if $A$ is row sparse, the speedup based on current quantum algorithms is quadratic.
Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax = b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300} times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.
We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithm for recommendation systems. Let $A in mathbb{C}^{m times n}$ be a rank-$k$ matrix, and $b in mathbb{C}^m$ be a vector. We present two algorithms: a sampling algorithm that provides a sample from $A^{-1}b$ and a query algorithm that outputs an estimate of an entry of $A^{-1}b$, where $A^{-1}$ denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity $O(mathrm{poly}(k, kappa, |A|_F, 1/epsilon),mathrm{polylog}(m, n))$, where $kappa$ is the condition number of $A$ and $epsilon$ is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that $A$ and $b$ come with well-known low-overhead data structures such that entries of $A$ and $b$ can be sampled according to some natural probability distributions. Alternatively, when $A$ is positive semidefinite, our algorithms can be adapted so that the sampling assumption on $b$ is not required.
We give efficient quantum algorithms to estimate the partition function of (i) the six vertex model on a two-dimensional (2D) square lattice, (ii) the Ising model with magnetic fields on a planar graph, (iii) the Potts model on a quasi 2D square lattice, and (iv) the Z_2 lattice gauge theory on a three-dimensional square lattice. Moreover, we prove that these problems are BQP-complete, that is, that estimating these partition functions is as hard as simulating arbitrary quantum computation. The results are proven for a complex parameter regime of the models. The proofs are based on a mapping relating partition functions to quantum circuits introduced in [Van den Nest et al., Phys. Rev. A 80, 052334 (2009)] and extended here.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
