Parallel Quantum Signal Processing Via Polynomial Factorization

• URL: http://arxiv.org/abs/2409.19043v1
• Date: Fri, 27 Sep 2024 17:54:30 GMT
• Title: Parallel Quantum Signal Processing Via Polynomial Factorization
• Authors: John M. Martyn, Zane M. Rossi, Kevin Z. Cheng, Yuan Liu, Isaac L. Chuang,
• Abstract summary: We develop a Quantum Parallel Signal Processing algorithm. Our algorithm parallelizes the computation of $texttr (P(rho)$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation suitable for quantum computers, and is realized at the expense of increasing the number of measurements by factor $O(textpoly(d) 2(k) )$.
• Score: 3.1981483719988235
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum signal processing (QSP) is a methodology for constructing polynomial transformations of a linear operator encoded in a unitary. Applied to an encoding of a state $\rho$, QSP enables the evaluation of nonlinear functions of the form $\text{tr}(P(\rho))$ for a polynomial $P(x)$, which encompasses relevant properties like entropies and fidelity. However, QSP is a sequential algorithm: implementing a degree-$d$ polynomial necessitates $d$ queries to the encoding, equating to a query depth $d$. Here, we reduce the depth of these property estimation algorithms by developing Parallel Quantum Signal Processing. Our algorithm parallelizes the computation of $\text{tr} (P(\rho))$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation algorithm suitable for distributed quantum computers, and is realized at the expense of increasing the number of measurements by a factor $O( \text{poly}(d) 2^{O(k)} )$. We achieve this result by factorizing $P(x)$ into a product of $k$ smaller polynomials of degree $O(d/k)$, which are each implemented in parallel with QSP, and subsequently multiplied together with a swap test to reconstruct $P(x)$. We characterize the achievable class of polynomials by appealing to the fundamental theorem of algebra, and demonstrate application to canonical problems including entropy estimation and partition function evaluation.

Related papers

• Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
  Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator. Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel. Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
  arXiv  Detail & Related papers  (2024-09-05T17:56:51Z)
• Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
  We develop a quantum eigensolver based on a D-Wave Quantum Annealer (D-Wave QA) This approach performs iterative QA measurements to optimize the eigenstates $vert psi rangle$ without the derivation of a classical computer. We confirm that the proposed QE algorithm provides exact solutions within the errors of $5 times 10-3$.
  arXiv  Detail & Related papers  (2024-06-05T15:19:53Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Generalized Quantum Signal Processing [0.6768558752130311]
  We present a Generalized Quantum Signal Processing approach, employing general SU(2) rotations as our signal processing operators. Our approach lifts all practical restrictions on the family of achievable transformations, with the sole remaining condition being that $|P|leq 1$. In cases where only $P$ is known, we provide an efficient GPU optimization capable of identifying in under a minute of time, a corresponding $Q$ for degree on the order of $107$.
  arXiv  Detail & Related papers  (2023-08-03T01:51:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Infinite quantum signal processing [1.3614427997190908]
  Quantum signal processing (QSP) represents a real scalar of degree $d$. We show that QSP can be used to represent a large class of non-polynomial functions. Our analysis reveals a surprising connection between the regularity of the target function and the decay properties of the factors.
  arXiv  Detail & Related papers  (2022-09-21T07:50:26Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  We propose a hybrid quantum-classical algorithm for solving linear systems on near-term quantum computers. We numerically solve non-trivial problems of size up to $250times250$ using Rigetti's quantum computer.
  arXiv  Detail & Related papers  (2019-09-12T17:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.