Approximating Korobov Functions via Quantum Circuits
- URL: http://arxiv.org/abs/2404.14570v1
- Date: Mon, 22 Apr 2024 20:33:53 GMT
- Title: Approximating Korobov Functions via Quantum Circuits
- Authors: Junaid Aftab, Haizhao Yang,
- Abstract summary: We explicitly construct quantum circuits that can approximate $d$-dimensional functions in the Korobov function space.
Our work provides quantitative approximation bounds and estimates the complexity of implementing the proposed quantum circuits.
- Score: 6.460951804337735
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing has the potential to address challenging problems in scientific computation. Therefore, it is important to analyze the capability of quantum circuits in solving computational problems from the perspective of approximation theory. In this paper, we explicitly construct quantum circuits that can approximate $d$-dimensional functions in the Korobov function space, $X^{2, p}([0,1]^d)$. We achieve this goal by leveraging the quantum signal processing algorithm and the linear combinations of unitaries technique to construct quantum circuits that implement Chebyshev polynomials which can approximate functions in $X^{2, p}([0,1]^d)$. Our work provides quantitative approximation bounds and estimates the complexity of implementing the proposed quantum circuits. Since $X^{2, p}(\Omega)$ is a subspace of Sobolev spaces, $W^{k,p}([0,1]^d)$, for $\max_{1 \leq i \leq d} k_i = 2$, our works develops a theoretical foundation to implement a large class of functions on a quantum computer. Our research adds to discussions about merging quantum computing techniques with scientific computing, suggesting promising paths for using quantum algorithms to solve challenging computational problems more efficiently.
Related papers
- A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
We introduce a novel quantum XZ24 algorithm, designed for efficiently computing the eigen-energy spectra of any quantum systems.
Compared to existing quantum methods, the new algorithm stands out for its remarkably low measurement cost.
We anticipate that the new algorithm will drive significant progress in quantum system simulation and offer promising applications in quantum computing and quantum information processing.
arXiv Detail & Related papers (2024-06-01T04:31:43Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods.
We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM)
The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
arXiv Detail & Related papers (2024-01-20T15:32:01Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems.
We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states.
Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
arXiv Detail & Related papers (2023-09-18T14:57:21Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
We develop a hybrid quantum-classical algorithm to estimate the partition function.
Our algorithm requires only a shallow $mathcalO(1)$-depth quantum circuit.
Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.
arXiv Detail & Related papers (2021-09-22T02:03:35Z) - Quantum advantage for computations with limited space [6.327095331866255]
We consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on.
We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$- by quantum circuits, leveraging custom two-qubit gates.
arXiv Detail & Related papers (2020-08-14T17:31:12Z) - 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.