Generalized Quantum Singular Value Transformation
- URL: http://arxiv.org/abs/2312.00723v1
- Date: Fri, 1 Dec 2023 16:59:14 GMT
- Title: Generalized Quantum Singular Value Transformation
- Authors: Christoph S\"underhauf
- Abstract summary: The quantum singular value transformation has revolutionised quantum algorithms.
By applying a computation to an arbitrary matrix, it provides a unifying picture of quantum algorithms.
Recent work has removed restrictions and enabled faster computation.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum singular value transformation has revolutionised quantum
algorithms. By applying a polynomial to an arbitrary matrix, it provides a
unifying picture of quantum algorithms. However, polynomials are restricted to
definite parity and real coefficients, and finding the circuit (the phase
factors) has proven difficult in practice. Recent work has removed these
restrictions and enabled faster computation of phase factors, yet only for
unitary matrices. Here we propose two generalisations. The generalised quantum
singular value transformation allows complex polynomials for arbitrary
matrices. For Hermitian matrices, we propose the generalised quantum eigenvalue
transformation that even allows polynomials of indefinite parity. While we find
that the polynomial might have to be downscaled compared to the quantum
singular value transformation, the higher expressivity of polynomials and
faster computation of phase factors can sometimes result in advantages. The
results are achieved with various block encoding (or projected unitary
encoding) techniques, including qubitisation, Hermitianisation, and
multiplication. We show how to multiply block-encoded matrices with only one
extra qubit, and introduce measure-early multiplication to further avoid the
extra qubit and decrease average circuit length.
Related papers
- Quantum eigenvalue processing [0.0]
Problems in linear algebra can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices.
We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary transformations on eigenvalues of block-encoded non-normal operators.
We also present a Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra.
arXiv Detail & Related papers (2024-01-11T19:49:31Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Quantum signal processing over SU(N) [0.0]
Quantum signal processing (QSP) and the quantum singular value transformation (QSVT) are pivotal tools for simplifying the development of quantum algorithms.
These techniques leverage transformations on the eigenvalues or singular values of block-encoded matrices, achieved with the use of just one control qubit.
In this work, we extend the original QSP ansatz by introducing multiple control qubits.
arXiv Detail & Related papers (2023-11-07T12:43:47Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Polynomial computational complexity of matrix elements of
finite-rank-generated single-particle operators in products of finite bosonic
states [0.0]
It is known that computing the permanent computation of the matrix $1+A$, where $A$ is a finite-rank matrix, requires a number of operations in the matrix size.
I extend this result to a generalization of the matrix permanent: an expectation value in a product of a large number of identical bosonic states with a bounded number of bosons.
arXiv Detail & Related papers (2022-10-20T20:09:28Z) - FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
We propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner.
FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates.
We show that FABLE circuits can be compressed and sparsified.
arXiv Detail & Related papers (2022-04-29T21:06:07Z) - Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices [4.2389474761558406]
We show how efficient quantum circuits can be explicitly constructed for some well-structured matrices.
We also provide implementations of these quantum circuits in sparse strategies.
arXiv Detail & Related papers (2022-03-19T03:50:16Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
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.