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
- 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) - A Generalized Space-Efficient Algorithm for Quantum Bit String
Comparators [0.0]
We introduce a design for the comparison of two $n$-qubit logic states using just two ancillary bits.
The work allows for sufficient flexibility in the design of quantum algorithms, which can accelerate quantum algorithm development.
arXiv Detail & Related papers (2023-11-11T14:01:35Z) - Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels.
RM codes only admit limited sets of rates.
Efficient decoders are available for RM codes at finite lengths.
arXiv Detail & Related papers (2023-01-16T04:11:14Z) - 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) - EfficientFCN: Holistically-guided Decoding for Semantic Segmentation [49.27021844132522]
State-of-the-art semantic segmentation algorithms are mostly based on dilated Fully Convolutional Networks (dilatedFCN)
We propose the EfficientFCN, whose backbone is a common ImageNet pre-trained network without any dilated convolution.
Such a framework achieves comparable or even better performance than state-of-the-art methods with only 1/3 of the computational cost.
arXiv Detail & Related papers (2020-08-24T14:48:23Z) - 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) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed.
An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed.
We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
arXiv Detail & Related papers (2020-06-15T02:57:57Z)
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.