Randomized semi-quantum matrix processing
- URL: http://arxiv.org/abs/2307.11824v2
- Date: Mon, 11 Sep 2023 10:11:05 GMT
- Title: Randomized semi-quantum matrix processing
- Authors: Allan Tosta, Thais de Lima Silva, Giancarlo Camilo, Leandro Aolita
- Abstract summary: We present a hybrid quantum-classical framework for Monte-Carlo simulation of generic matrix functions.
Our framework provides a pathway towards early fault-tolerant quantum linear algebra applications.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computers have the potential to speed-up important matrix-arithmetic
tasks. A prominent framework for that is the quantum singular-value
transformation (QSVT) formalism, which uses Chebyshev approximations and
coherent access to the input matrix via a unitary block encoding to design a
target matrix function. Nonetheless, physical implementations for useful
end-user applications require large-scale fault-tolerant quantum computers.
Here, we present a hybrid quantum-classical framework for Monte-Carlo
simulation of generic matrix functions more amenable to early fault-tolerant
quantum hardware. Serving from the ideas of QSVT, we randomize over the
Chebyshev polynomials while keeping the matrix oracle quantum. The method is
assisted by a variant of the Hadamard test that removes the need for
post-selection. As a result, it features a similar statistical overhead to the
fully quantum case of standard QSVT and does not incur any circuit depth
degradation. On the contrary, the average circuit depth is shown to get
smaller, yielding equivalent reductions of noise sensitivity, as we explicitly
show for depolarizing noise and coherent errors. We apply our technique to four
specific use cases: partition-function estimation via quantum Markov-chain
Monte Carlo and via imaginary-time evolution; end-to-end linear system solvers;
and ground-state energy estimation. For these cases, we prove advantages on
average depths, including quadratic speed-ups on costly parameters and even the
removal of the approximation-error dependence. All in all, our framework
provides a pathway towards early fault-tolerant quantum linear algebra
applications.
Related papers
- Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation [0.0]
This paper proposes a hybrid quantum-classical algorithm for compiling the time-evolution operator.
It achieves a 95% reduction in circuit depth compared to Trotterization while maintaining accuracy.
We estimate the gate count needed to execute the quantum simulations using the LSVQC on near-term quantum computing architectures.
arXiv Detail & Related papers (2024-07-19T09:50:01Z) - Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.
We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.
We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
arXiv Detail & Related papers (2024-05-03T17:32:55Z) - Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
We present variational quantum algorithms (VQAs) that encode both space and time in qubit registers.
The spacetime encoding enables us to obtain the entire time evolution from a single ground-state computation.
arXiv Detail & Related papers (2024-03-25T14:06:18Z) - Pre-optimizing variational quantum eigensolvers with tensor networks [1.4512477254432858]
We present and benchmark an approach where we find good starting parameters for parameterized quantum circuits by simulating VQE.
We apply this approach to the 1D and 2D Fermi-Hubbard model with system sizes that use up to 32 qubits.
In 2D, the parameters that VTNE finds have significantly lower energy than their starting configurations, and we show that starting VQE from these parameters requires non-trivially fewer operations to come down to a given energy.
arXiv Detail & Related papers (2023-10-19T17:57:58Z) - 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) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem.
The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
arXiv Detail & Related papers (2022-05-31T00:14:49Z) - Dequantizing the Quantum Singular Value Transformation: Hardness and
Applications to Quantum Chemistry and the Quantum PCP Conjecture [0.0]
We show that the Quantum Singular Value Transformation can be efficiently "dequantized"
We show that with inverse-polynomial precision, the same problem becomes BQP-complete.
We also discuss how this dequantization technique may help make progress on the central quantum PCP.
arXiv Detail & Related papers (2021-11-17T12:50:13Z) - 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) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations.
We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
arXiv Detail & Related papers (2021-03-12T20:58:41Z) - Variational Quantum Singular Value Decomposition [8.145223158030259]
We propose a variational quantum algorithm for singular value decomposition (VQSVD)
By exploiting the variational principles for singular values and the Ky Fan Theorem, we design a novel loss function such that two quantum neural networks could be trained to learn the singular vectors and output the corresponding singular values.
Our work explores new avenues for quantum information processing beyond the conventional protocols that only works for Hermitian data.
arXiv Detail & Related papers (2020-06-03T15:32:08Z) - 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.