Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Contributions to Information-Based Complexity and to Quantum Computing

Petras, Iasonas

Published Jan 1, 2013• 0 citations
Publisher

Abstract

Multivariate continuous problems are widely encountered in physics, chemistry, finance and in computational sciences. Unfortunately, interesting real world multivariate continuous problems can almost never be solved analytically. As a result, they are typically solved numerically and therefore approximately. In this thesis we deal with the approximate solution of multivariate problems. The complexity of such problems in the classical setting has been extensively studied in the literature. On the other hand the quantum computational model presents a promising alternative for dealing with multivariate problems. The idea of using quantum mechanics to simulate quantum physics was initially proposed by Feynman in 1982. Its potential was demonstrated by Shor's integer factorization algorithm, which exponentially improves the cost of the best classical algorithm known. In the first part of this thesis we study the tractability of multivariate problems in the worst and average case settings using the real number model with oracles. We derive necessary and sufficient conditions for weak tractability for linear multivariate tensor product problems in those settings. More specifically, we initially study necessary and sufficient conditions for weak tractability on linear multivariate tensor product problems in the worst case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the squares of the singular values of the solution operator for the univariate problem. We show a condition on the singular values that is sufficient for weak tractability. The same condition is known to be necessary for weak tractability. Then, we study linear multivariate tensor product problems in the average case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the eigenvalues of the covariance operator of the induced measure of the one dimensional problem. We derive a necessary and sufficient condition on the eigenvalues for such problems to be weakly tractable but not polynomially tractable. In the second part of this thesis we study quantum algorithms for certain eigenvalue problems and the implementation and design of quantum circuits for a modification of the quantum NAND evaluation algorithm on k-ary trees, where k is a constant. First, we study quantum algorithms for the estimation of the ground state energy of the multivariate time-independent Schrodinger equation corresponding to a multiparticle system in a box. The dimension d of the problem depends linearly to the number of particles of the system. We design a quantum algorithm that approximates the lowest eigenvalue with relative error ε for a non-negative potential V, where V as well as its first order partial derivatives are continuous and uniformly bounded by one. The algorithm requires a number of quantum operations that depends polynomially on the inverse of the accuracy and linearly on the number of the particles of the system. We note that the cost of any classical deterministic algorithm grows exponentially in the number of particles. Thus we have an exponential speedup with respect to the dimension of the problem d, when compared to the classical deterministic case. We extend our results to convex non-negative potentials V, where V as well as its first order partial derivatives are continuous and uniformly bounded by constants C and C' respectively. The algorithm solves the eigenvalue problem for a sequence of convex potentials in order to obtain its final result. More specifically, the quantum algorithm estimates the ground state energy with relative error ε a number of quantum operations that depends polynomially on the inverse of the accuracy, the uniform bound C on the potential and the dimension d of the problem. In addition, we present a modification of the algorithm that produces a quantum state which approximates the ground state eigenvector of the discretized Hamiltonian within Δ. This algorithm requires a number of quantum operations that depends pollynomially on the inverse of ε, the inverse of Δ, the uniform bound C on the potential and the dimension d of the problem. Finally, we consider the algorithm by Ambainis et.al. that evaluates balanced binary NAND formulas. We design a quantum circuit that implements a modification of the algorithm for k-ary trees, where k is a constant. Furthermore, we design another quantum circuit that consists exclusively of Clifford and T gates. This circuit approximates the previous one with error ε using the Solovay-Kitaev algorithm.

DOI
10.7916/d80v8m04

Related papers

Quantum Algorithms and Complexity for Numerical Problems

Zhang, Chi

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.

•Jan 1, 2011•0 citations

Quantum Algorithms and Complexity for Certain Continuous and Related Discrete Problems

Kwas, Marek

The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.

•Jan 1, 2005•3 citations

Multivariate Quantum Signal Processing

Guang Hao Low

We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under $H=\sum_j H_j$ with weighted quasinorm cost $\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))$ for block-encoding normalizations $\vecλ$ and costs $\vec C$; (2) sparse simulation with optimal time--norm $Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)$ and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost $t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}$ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.

quant-pharXiv:2610.01125•Oct 2, 2026•2 citations

Quantum Algorithms for Scientific Computing and Approximate Optimization

Stuart Hadfield

Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.

arXiv:1805.03265•Jan 1, 2018•79 citations

On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics

Joseph F. Traub, Arvid J. Bessen

Our understanding of complex mechanical processes is by our inability to solve the equations that govern them except for simple cases. Numerical simulation of systems appears to be our best option to understand, design and improve systems. It turns out, however, that computational problems in mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem. One of the most radical approaches for treating problems was proposed by Feytiman in 1982 [46]: he suggested that mechanics itself showed a promising way to simulate physics. This idea, the so called computer, showed its potential convincingly in one important regime with the development of Shor's integer factorization algorithm which improves exponentially on the best known classical algorithm. In this thesis we explore six different computational problems from mechanics, study their computational complexity and try to find ways to remedy them. In the first problem we investigate the reasons behind the improved performance of Shor's and similar algorithms. We show that the key part in Shor's algorithm, the phase estimation algorithm, achieves its good performance through the use of power queries and we give lower bounds for all phase estimation algorithms that use power queries that match the known upper bounds. Our research indicates that problems that allow the use of power queries will achieve similar exponential improvements over classical algorithms. We then apply our lower bound technique for power queries to the Sturm-Liouville eigenvalue problem and show matching lower bounds to the upper bounds of Papageorgiou and Wozniakowski [85]. It seems to be very difficult, though, to find nontrivial instances of the Sturm-Lionville problem for which power queries can be simulated efficiently. A computer differs from a classical computer that uses randomness, because it allows negative probabilities that can cancel each other (destructive interference). Ideally we would like to transfer classical randomized algorithms to the computer and get speed improvements. One of the simplest classical randomized algorithm is the random walk and we study the behavior of the continuous-time random walk. We analyze this random walk in one dimension and give analytical formulas for its behavior that demonstrate its interference properties. Is interference or cancellation really the most important advantage that a computer has over a classical computer? To answer that question we study the class StociMA of stochastic quantum algorithms that only use classical gates, but are given a witness, i.e. an arbitrary state that can guide the algorithm in computing the correct answer, but should not be able to fool it. We show that there exists a complete problem for this class, which we call the stoquastic local Hamiltonian problem. In this problem we try to compute the lowest eigenvalue of a Hamiltonian with interactions that span only a fixed number of particles and all contribute negatively. With the help of this problem we prove that MA ⊆ StocIMA ⊆ SBP ∪ QMA. This shows that interference is one of the most important parts of computation. The simulation of the evolution of a general system in time requires a computational time that is exponential in the dimension of the system. But maybe the problem that we ask for is too general and we can simulate special systems in polynomial time. In particular it would be interesting to study systems of limited energy, i.e. for which the state at starting time consists mainly out of components with small energy. We model this in the theory of weighted reproducing kernel Hilbert spaces with two different sets of weights: product weights and finite-order weights. We will show that the information cost of computing the evolution for starting states from these spaces is tractable, i.e. the cost does not grow exponentially with the dimension of the problem. Finally we study a computational problem from lattice chromodynamics (QCD). In most popular algorithms that treat problems in QCD the (gauged) Dirac matrix has to be inverted numerous times. Since this matrix is large, sparse, and ill-conditioned, iterative approaches have to be used. Unfortunately a direct application of methods like conjugate gradient (CC) or minimal residual algorithms seem to give poor performance in practice. We study a newly proposed multigrid method, adaptive smoothed aggregation [29], that has promise to overcome these difficulties We show that while classical CG's convergence becomes worse as the matrix becomes almost singular, adaptive smoothed aggregation will still perform well.

•Jan 1, 2008•2 citations

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations
Multivariate continuous problems are widely encountered in physics, chemistry, finance and in computational sciences. Unfortunately, interesting real world multivariate continuous problems can almost never be solved analytically. As a result, they are typically solved numerically and therefore approximately. In this thesis we deal with the approximate solution of multivariate problems. The complexity of such problems in the classical setting has been extensively studied in the literature. On the other hand the quantum computational model presents a promising alternative for dealing with multivariate problems. The idea of using quantum mechanics to simulate quantum physics was initially proposed by Feynman in 1982. Its potential was demonstrated by Shor's integer factorization algorithm, which exponentially improves the cost of the best classical algorithm known. In the first part of this thesis we study the tractability of multivariate problems in the worst and average case settings using the real number model with oracles. We derive necessary and sufficient conditions for weak tractability for linear multivariate tensor product problems in those settings. More specifically, we initially study necessary and sufficient conditions for weak tractability on linear multivariate tensor product problems in the worst case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the squares of the singular values of the solution operator for the univariate problem. We show a condition on the singular values that is sufficient for weak tractability. The same condition is known to be necessary for weak tractability. Then, we study linear multivariate tensor product problems in the average case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the eigenvalues of the covariance operator of the induced measure of the one dimensional problem. We derive a necessary and sufficient condition on the eigenvalues for such problems to be weakly tractable but not polynomially tractable. In the second part of this thesis we study quantum algorithms for certain eigenvalue problems and the implementation and design of quantum circuits for a modification of the quantum NAND evaluation algorithm on k-ary trees, where k is a constant. First, we study quantum algorithms for the estimation of the ground state energy of the multivariate time-independent Schrodinger equation corresponding to a multiparticle system in a box. The dimension d of the problem depends linearly to the number of particles of the system. We design a quantum algorithm that approximates the lowest eigenvalue with relative error ε for a non-negative potential V, where V as well as its first order partial derivatives are continuous and uniformly bounded by one. The algorithm requires a number of quantum operations that depends polynomially on the inverse of the accuracy and linearly on the number of the particles of the system. We note that the cost of any classical deterministic algorithm grows exponentially in the number of particles. Thus we have an exponential speedup with respect to the dimension of the problem d, when compared to the classical deterministic case. We extend our results to convex non-negative potentials V, where V as well as its first order partial derivatives are continuous and uniformly bounded by constants C and C' respectively. The algorithm solves the eigenvalue problem for a sequence of convex potentials in order to obtain its final result. More specifically, the quantum algorithm estimates the ground state energy with relative error ε a number of quantum operations that depends polynomially on the inverse of the accuracy, the uniform bound C on the potential and the dimension d of the problem. In addition, we present a modification of the algorithm that produces a quantum state which approximates the ground state eigenvector of the discretized Hamiltonian within Δ. This algorithm requires a number of quantum operations that depends pollynomially on the inverse of ε, the inverse of Δ, the uniform bound C on the potential and the dimension d of the problem. Finally, we consider the algorithm by Ambainis et.al. that evaluates balanced binary NAND formulas. We design a quantum circuit that implements a modification of the algorithm for k-ary trees, where k is a constant. Furthermore, we design another quantum circuit that consists exclusively of Clifford and T gates. This circuit approximates the previous one with error ε using the Solovay-Kitaev algorithm.
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.
The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices. Our framework equips quantum transducers with the analytic structure of multiport Infinite-Impulse-Response (IIR) filters and establishes a transfer-function methodology for designing quantum query algorithms. Efficiently computable analytic bounds that hold uniformly across the oracle promise yield efficient quantum circuits with logarithmic error dependence and near-unity success probability, paralleling the approximation-theoretic guarantees of univariate QSP/QSVT. We provide a complete characterization of achievable transfer functions and a principled library of analytic IIR components. Our modular designs greatly improve or resolve the per-oracle query complexity of open multi-oracle problems: (1) Hamiltonian simulation under H=∑jHjH=\sum_j H_jH=∑j​Hj​ with weighted quasinorm cost ≈t⟨λ⃗,C⃗⟩1/2+O(∥C⃗∥1log⁡(1/ε))\approx t\langle\vecλ,\vec C\rangle_{1/2}+\mathcal{O}(\|\vec C\|_1\log(1/ε))≈t⟨λ,C⟩1/2​+O(∥C∥1​log(1/ε)) for block-encoding normalizations λ⃗\vecλλ and costs C⃗\vec CC; (2) sparse simulation with optimal time--norm Θ(d∥H∥1→2t)Θ(\sqrt{d}\|H\|_{\rm 1\to2}t)Θ(d​∥H∥1→2​t) and additive error dependence; (3) solving linear systems and (4) differential equations under minimal matrix assumptions with optimal weighted state-preparation and multi-term cost; (5) ground-state preparation and energy estimation; (6) generalized eigenvalue problems. We apply these to exactly simulate downfolded Hamiltonians with leading cost t⟨λ⃗eff,C⃗eff⟩1/2t\langle\vecλ_{\rm eff},\vec C_{\rm eff}\rangle_{1/2}t⟨λeff​,Ceff​⟩1/2​ further reduced by fractional dynamic correlation energy contributions from coarse-grained Hamiltonians, and show similar classical-data-input-reduction results for multiscale graph classification via Kron reduction. We also show the online generalization with anisotropic Kalman filtering of streaming quantum data.
Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we study the application of quantum computers to computational problems in science and engineering, and to combinatorial optimization problems. We outline the results below. Algorithms for scientific computing require modules, i.e., building blocks, implementing elementary numerical functions that have well-controlled numerical error, are uniformly scalable and reversible, and that can be implemented efficiently. We derive quantum algorithms and circuits for computing square roots, logarithms, and arbitrary fractional powers, and derive worst-case error and cost bounds. We describe a modular approach to quantum algorithm design as a first step towards numerical standards and mathematical libraries for quantum scientific computing. A fundamental but computationally hard problem in physics is to solve the time-independent Schrödinger equation. This is accomplished by computing the eigenvalues of the corresponding Hamiltonian operator. The eigenvalues describe the different energy levels of a system. The cost of classical deterministic algorithms computing these eigenvalues grows exponentially with the number of system degrees of freedom. The number of degrees of freedom is typically proportional to the number of particles in a physical system. We show an efficient quantum algorithm for approximating a constant number of low-order eigenvalues of a Hamiltonian using a perturbation approach. We apply this algorithm to a special case of the Schrödinger equation and show that our algorithm succeeds with high probability, and has cost that scales polynomially with the number of degrees of freedom and the reciprocal of the desired accuracy. This improves and extends earlier results on quantum algorithms for estimating the ground state energy. We consider the simulation of quantum mechanical systems on a quantum computer. We show a novel divide and conquer approach for Hamiltonian simulation. Using the Hamiltonian structure, we can obtain faster simulation algorithms. Considering a sum of Hamiltonians we split them into groups, simulate each group separately, and combine the partial results. Simulation is customized to take advantage of the properties of each group, and hence yield refined bounds to the overall simulation cost. We illustrate our results using the electronic structure problem of quantum chemistry, where we obtain significantly improved cost estimates under mild assumptions. We turn to combinatorial optimization problems. An important open question is whether quantum computers provide advantages for the approximation of classically hard combinatorial problems. A promising recently proposed approach of Farhi et al. is the Quantum Approximate Optimization Algorithm (QAOA). We study the application of QAOA to the Maximum Cut problem, and derive analytic performance bounds for the lowest circuit-depth realization, for both general and special classes of graphs. Along the way, we develop a general procedure for analyzing the performance of QAOA for other problems, and show an example demonstrating the difficulty of obtaining similar results for greater depth. We show a generalization of QAOA and its application to wider classes of combinatorial optimization problems, in particular, problems with feasibility constraints. We introduce the Quantum Alternating Operator Ansatz, which utilizes more general unitary operators than the original QAOA proposal. Our framework facilitates low-resource implementations for many applications which may be particularly suitable for early quantum computers. We specify design criteria, and develop a set of results and tools for mapping diverse problems to explicit quantum circuits. We derive constructions for several important prototypical problems including Maximum Independent Set, Graph Coloring, and the Traveling Salesman problem, and show appealing resource cost estimates for their implementations.
Our understanding of complex mechanical processes is by our inability to solve the equations that govern them except for simple cases. Numerical simulation of systems appears to be our best option to understand, design and improve systems. It turns out, however, that computational problems in mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem. One of the most radical approaches for treating problems was proposed by Feytiman in 1982 [46]: he suggested that mechanics itself showed a promising way to simulate physics. This idea, the so called computer, showed its potential convincingly in one important regime with the development of Shor's integer factorization algorithm which improves exponentially on the best known classical algorithm. In this thesis we explore six different computational problems from mechanics, study their computational complexity and try to find ways to remedy them. In the first problem we investigate the reasons behind the improved performance of Shor's and similar algorithms. We show that the key part in Shor's algorithm, the phase estimation algorithm, achieves its good performance through the use of power queries and we give lower bounds for all phase estimation algorithms that use power queries that match the known upper bounds. Our research indicates that problems that allow the use of power queries will achieve similar exponential improvements over classical algorithms. We then apply our lower bound technique for power queries to the Sturm-Liouville eigenvalue problem and show matching lower bounds to the upper bounds of Papageorgiou and Wozniakowski [85]. It seems to be very difficult, though, to find nontrivial instances of the Sturm-Lionville problem for which power queries can be simulated efficiently. A computer differs from a classical computer that uses randomness, because it allows negative probabilities that can cancel each other (destructive interference). Ideally we would like to transfer classical randomized algorithms to the computer and get speed improvements. One of the simplest classical randomized algorithm is the random walk and we study the behavior of the continuous-time random walk. We analyze this random walk in one dimension and give analytical formulas for its behavior that demonstrate its interference properties. Is interference or cancellation really the most important advantage that a computer has over a classical computer? To answer that question we study the class StociMA of stochastic quantum algorithms that only use classical gates, but are given a witness, i.e. an arbitrary state that can guide the algorithm in computing the correct answer, but should not be able to fool it. We show that there exists a complete problem for this class, which we call the stoquastic local Hamiltonian problem. In this problem we try to compute the lowest eigenvalue of a Hamiltonian with interactions that span only a fixed number of particles and all contribute negatively. With the help of this problem we prove that MA ⊆ StocIMA ⊆ SBP ∪ QMA. This shows that interference is one of the most important parts of computation. The simulation of the evolution of a general system in time requires a computational time that is exponential in the dimension of the system. But maybe the problem that we ask for is too general and we can simulate special systems in polynomial time. In particular it would be interesting to study systems of limited energy, i.e. for which the state at starting time consists mainly out of components with small energy. We model this in the theory of weighted reproducing kernel Hilbert spaces with two different sets of weights: product weights and finite-order weights. We will show that the information cost of computing the evolution for starting states from these spaces is tractable, i.e. the cost does not grow exponentially with the dimension of the problem. Finally we study a computational problem from lattice chromodynamics (QCD). In most popular algorithms that treat problems in QCD the (gauged) Dirac matrix has to be inverted numerous times. Since this matrix is large, sparse, and ill-conditioned, iterative approaches have to be used. Unfortunately a direct application of methods like conjugate gradient (CC) or minimal residual algorithms seem to give poor performance in practice. We study a newly proposed multigrid method, adaptive smoothed aggregation [29], that has promise to overcome these difficulties We show that while classical CG's convergence becomes worse as the matrix becomes almost singular, adaptive smoothed aggregation will still perform well.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.