Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices

• URL: http://arxiv.org/abs/2410.05241v1
• Date: Mon, 7 Oct 2024 17:44:30 GMT
• Title: Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices
• Authors: Sunheang Ty, Renaud Vilmart, Axel TahmasebiMoradi, Chetra Mang,
• Abstract summary: Solving differential equations is one of the most computationally expensive problems in classical computing. Despite recent progress made in the field of quantum computing and quantum algorithms, its end-to-end application towards practical realization still remains unattainable.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving differential equations is one of the most computationally expensive problems in classical computing, occupying the vast majority of high-performance computing resources devoted towards practical applications in various fields of science and engineering. Despite recent progress made in the field of quantum computing and quantum algorithms, its end-to-end application towards practical realization still remains unattainable. In this article, we tackle one of the primary obstacles towards this ultimate objective, specifically the encoding of matrices derived via finite difference method solving Poisson partial differential equations in simple boundary-value problems. To that end, we propose a novel methodology called block-diagonalization, which provides a common decomposition form for our matrices, and similarly a common procedure for block-encoding these matrices inside a unitary operator of a quantum circuit. The depth of these circuits is double-logarithmic in the matrix size, which is an exponential improvement over existing quantum methods and a superexponential improvement over existing classical methods. These improvements come at the price of a constant multiplicative overhead on the number of qubits and the number of gates. Combined with quantum linear solver algorithms, we can utilize these quantum circuits to produce a quantum state representation of the solution to the Poisson partial differential equations and their boundary-value problems.

Related papers

• Automated Synthesis of Quantum Algorithms via Classical Numerical Techniques [2.7536859673878857]
  We apply numerical optimization and linear algebra algorithms for classical computers to the problem of automatically synthesizing algorithms for quantum computers. Our methods are evaluated on single-qubit systems as well as on larger systems.
  arXiv  Detail & Related papers  (2024-08-27T17:43:58Z)
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics [14.379311972506791]
  We propose quantum methods for solving differential equations based on a gradual improvement of the solution via an iterative process. We benchmark the approach on paradigmatic fluid dynamics problems.
  arXiv  Detail & Related papers  (2024-04-12T17:08:27Z)
• Efficient Quantum Circuits for Non-Unitary and Unitary Diagonal Operators with Space-Time-Accuracy trade-offs [1.0749601922718608]
  Unitary and non-unitary diagonal operators are fundamental building blocks in quantum algorithms. We introduce a general approach to implement unitary and non-unitary diagonal operators with efficient-adjustable-depth quantum circuits.
  arXiv  Detail & Related papers  (2024-04-03T15:42:25Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Depth analysis of variational quantum algorithms for heat equation [0.0]
  We consider three approaches to solve the heat equation on a quantum computer. An exponential number of Pauli products in the Hamiltonian decomposition does not allow for the quantum speed up to be achieved. The ansatz tree approach exploits an explicit form of the matrix what makes it possible to achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2022-12-23T14:46:33Z)
• 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 circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most. We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
  arXiv  Detail & Related papers  (2022-04-12T19:39:31Z)
• 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)
• 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)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)

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.