We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.
We study the complexity of a two-point boundary value problem. We concentrate on the linear problem of order k with separated boundary conditions. Right-hand side functions are assumed to be r times differentiable with all derivatives bounded by a constant. We consider three models of computation: deterministic with standard and linear information, randomized and quantum. In each setting, we construct an algorithm for solving the problem, which allows us to establish upper complexity bounds. In the deterministic setting, we show that the use of linear information gives us a speed-up of at least one order of magnitude compared with the standard information. For randomized algorithms, we show that the speed-up over standard deterministic algorithms is by 1/2 in the exponent. For quantum algorithms, we can achieve a speed-up by one order of magnitude. We also provide lower complexity bounds. They match upper bounds in the deterministic setting with the standard information, and almost match upper bounds in the randomized and quantum settings. In the deterministic setting with the linear information, a gap still remains between the upper and lower complexity bounds.
The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the ε-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The ε-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by 1/2, and quantum algorithms by 1 in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.
We study possible advantages of randomized and quantum computing over deterministic computing for scalar initial-value problems for ordinary differential equations of order k. For systems of equations of the first order this question has been settled modulo some details in \cite{Kacewicz05}. A speed-up over deterministic computing shown in \cite{Kacewicz05} is related to the increased regularity of the solution with respect to that of the right-hand side function. For a scalar equation of order k (which can be transformed into a special system of the first order), the regularity of the solution is increased by k orders of magnitude. This leads to improved complexity bounds depending on k for linear information in the deterministic setting, see \cite{Szczesny05}. This may suggest that in the randomized and quantum settings a speed-up can also be achieved depending on k. We show in this paper that a speed-up dependent on k is not possible in the randomized and quantum settings. We establish lower complexity bounds, showing that the randomized and quantum complexities remain at the some level as for systems of the first order, no matter how large k is. Thus, the algorithms from \cite{Kacewicz05} remain (almost) optimal, even if we restrict ourselves to a subclass of systems arising from scalar equations of order k.
The complexity of the following numerical problem is studied in the quantum model of computation: Consider a general elliptic partial differential equation of order 2m in a smooth, bounded domain Q\\subset \\R^d with smooth coefficients and homogeneous boundary conditions. We seek to approximate the solution on a smooth submanifold M\\subseteq Q of dimension 0\\le d_1 \\le d. With the right hand side belonging to C^r(Q), and the error being measured in the L_\\infty(M) norm, we prove that the n-th minimal quantum error is (up to logarithmic factors) of order n^{-min((r+2m)/d_1,r/d+1)}. For comparison, in the classical deterministic setting the n-th minimal error is known to be of order n^{-r/d}, for all d_1, while in the classical randomized setting it is (up to logarithmic factors) n^{-min((r+2m)/d_1,r/d+1/2)}.
In this paper we study the quantum complexity of the integration of a function with an unknown singularity. We assume that the function has r continuous derivatives, with the derivative of order r being H\"older continuous with the exponent ρ on the whole integration interval except the one singular point. We show that the $\ve$-complexity of this problem is of order $\ve^{-1/(r+\rho+1)}$. Since the classical deterministic complexity of this problem is $\ve^{-1/(r+\rho)}$, quantum computers give a speed-up for this problem for all values of parameters r and ρ.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
New lower bounds for CDS and f-routing
Understanding the entanglement cost of non-local quantum computation (NLQC) is relevant to complexity theory, cryptography, quantum gravity, and other areas. A central special case is f-routing, motivated in part by quantum position verification. Proving lower bounds on its entanglement cost in the fully robust setting has been a major open problem in NLQC.
Motivated by this problem, we establish two related lower bounds. First, we study the shared-randomness cost of robust conditional disclosure of secrets (CDS). The connection between CDS and f-routing established by Allerstorfer et al. (Quantum 2024) makes understanding the randomness complexity of robust CDS a natural step toward lower bounds for the fully robust routing problem. We show that the shared-randomness cost of robust CDS is lower bounded by the logarithm of deterministic SMP communication complexity, even when communication and private randomness are unrestricted. Our lower bound is tight for the equality function.
Second, we consider one-sided-perfect f-routing, in which the protocol is exact on one input class and has constant error on the other. By exploiting the positivity of the low-rank matrix in the method of Asadi, Culf, and May (ITCS 2025), we derive a lower bound on the entanglement cost in terms of sign rank. In particular, this yields a linear lower bound on the entanglement cost of routing for the inner-product function in both one-sided-perfect settings, matching the known upper bound.