On efficient quantum block encoding of pseudo-differential operators
- URL: http://arxiv.org/abs/2301.08908v3
- Date: Wed, 31 May 2023 05:11:07 GMT
- Title: On efficient quantum block encoding of pseudo-differential operators
- Authors: Haoya Li, Hongkang Ni, Lexing Ying
- Abstract summary: Block encoding lies at the core of many existing quantum algorithms.
This paper presents a study of the block encoding of a rich family of dense operators: the pseudo-differential operators (PDOs)
- Score: 6.134067544403308
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Block encoding lies at the core of many existing quantum algorithms.
Meanwhile, efficient and explicit block encodings of dense operators are
commonly acknowledged as a challenging problem. This paper presents a
comprehensive study of the block encoding of a rich family of dense operators:
the pseudo-differential operators (PDOs). First, a block encoding scheme for
generic PDOs is developed. Then we propose a more efficient scheme for PDOs
with a separable structure. Finally, we demonstrate an explicit and efficient
block encoding algorithm for PDOs with a dimension-wise fully separable
structure. Complexity analysis is provided for all block encoding algorithms
presented. The application of theoretical results is illustrated with worked
examples, including the representation of variable coefficient elliptic
operators and the computation of the inverse of elliptic operators without
invoking quantum linear system algorithms (QLSAs).
Related papers
- A Theoretical Perspective for Speculative Decoding Algorithm [60.79447486066416]
One effective way to accelerate inference is emphSpeculative Decoding, which employs a small model to sample a sequence of draft tokens and a large model to validate.
This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, emphoutput quality and inference acceleration, from a theoretical perspective.
arXiv Detail & Related papers (2024-10-30T01:53:04Z) - Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
In this paper, we aim to characterize the gates of quantum Reed-Muller (RM) codes by exploiting the well-studied properties of their classical counterparts.
A set of stabilizer generators for a RM code can be described via $X$ and $Z$ operators acting on subcubes of particular dimensions.
arXiv Detail & Related papers (2024-10-10T04:07:24Z) - A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions [0.0]
We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms.
We consider the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256.
For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low.
arXiv Detail & Related papers (2024-09-10T18:46:26Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Block encoding of sparse structured matrices coming from ocean acoustics in quantum computing [2.4487770108795393]
Block encoding is a data input model commonly used in a quantum computer.
New base scheme of block encoding is given which generalizes the one in citecamps2024 by removing the constraint that every data item should appear in all columns.
arXiv Detail & Related papers (2024-05-28T09:49:58Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - 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) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - Glushkov's construction for functional subsequential transducers [91.3755431537592]
Glushkov's construction has many interesting properties and they become even more evident when applied to transducers.
Special flavour of regular expressions is introduced, which can be efficiently converted to $epsilon$-free functional subsequential weighted finite state transducers.
arXiv Detail & Related papers (2020-08-05T17:09:58Z) - Approximate Quantum Circuit Synthesis using Block-Encodings [0.0]
One of the challenges in quantum computing is the synthesis of unitary operators into quantum circuits with polylogarithmic gate complexity.
We propose a novel approximate quantum circuit synthesis technique by relaxing the unitary constraints and interchanging them for ancilla qubits via block-encodings.
arXiv Detail & Related papers (2020-07-02T22:30:28Z)
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.