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

Physica A Statistical Mechanics and its Applications

An almost integrable quantum system in 1 + ε dimensions

Th.W. Ruijgrok, K. Sokalski

Published Jul 1, 1994• 1 citation
Publisher
DOI
10.1016/0378-4371(94)00037-9

Related papers

Coin Tossing Algorithms for Integral Equations and Tractability

Erich Novak, Harald Pfeiffer

Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d . This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε −2 function values and only d log 2 ε random bits. The number of arithmetic operations is of the order ε −2 + d log 2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d , we obtain the upper bound C · (ε −2 + d log 2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.

Monte Carlo Methods and Applications•Jan 1, 2004•6 citations

Quantum integrable systems in one dimension

Michael Fowler

arXiv:cond-mat/9401051•Physica D Nonlinear Phenomena•Sep 1, 1995•2 citations

Efficient quantum simulation algorithms in the path integral formulation

Serene Shum, Nathan Wiebe

Abstract We provide a new paradigm for quantum simulation based on path integration that allows quantum speedups to be observed for problems that are more naturally expressed using the path integral formalism rather than the conventional Hamiltonian formalism. We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form m 2 x ˙ 2 − V ( x ) , while avoiding the sign problems that preclude efficient Monte-Carlo algorithms for such problems. This Lagrangian path integral algorithm is based on a new rigorous derivation of a discrete version of the Lagrangian path integral. Our first Hamiltonian path integral method breaks up the paths into short timesteps. It is efficient under appropriate sparsity assumptions and requires a number of queries to oracles that give the eigenvalues and overlaps between the eigenvectors of the Hamiltonian terms that scales as t o ( 1 ) / ϵ o ( 1 ) for simulation time t and error ϵ . The second approach uses long-time path integrals for near-adiabatic systems and has query complexity that scales as O ( 1 / ϵ ) if the energy eigenvalue gaps and simulation time is sufficiently long. Finally, we show that our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales for a system with η particles in D + 1 dimensions as O ~ ( η D t 2 / ϵ ) if V ( x ) is bounded and finite and the wavefunction obeys appropriate position and momentum cutoffs. This shows that Lagrangian dynamics can be efficiently simulated on quantum computers and opens up the possibility for quantum field theories for which the Hamiltonian is unknown to be efficiently simulated on quantum computers.

arXiv:2405.07042•Journal of Physics A Mathematical and Theoretical•May 29, 2026•1 citation

IN QUANTUM COMPLETELY INTEGRABLE MODELS

Anton Vladimirovich Zabrodin

•Jan 1, 1987•0 citations

Quantum integrable systems

Miki Wadati, Taro Nagao, Kazuhiro Hikami

Physica D Nonlinear Phenomena•Sep 1, 1993•10 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })

Mathematics of Computation•Jun 25, 2002•56 citations
Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d . This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε −2 function values and only d log 2 ε random bits. The number of arithmetic operations is of the order ε −2 + d log 2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d , we obtain the upper bound C · (ε −2 + d log 2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.
Abstract We provide a new paradigm for quantum simulation based on path integration that allows quantum speedups to be observed for problems that are more naturally expressed using the path integral formalism rather than the conventional Hamiltonian formalism. We provide two novel quantum algorithms based on Hamiltonian versions of the path integral formulation and another for Lagrangians of the form m 2 x ˙ 2 − V ( x ) , while avoiding the sign problems that preclude efficient Monte-Carlo algorithms for such problems. This Lagrangian path integral algorithm is based on a new rigorous derivation of a discrete version of the Lagrangian path integral. Our first Hamiltonian path integral method breaks up the paths into short timesteps. It is efficient under appropriate sparsity assumptions and requires a number of queries to oracles that give the eigenvalues and overlaps between the eigenvectors of the Hamiltonian terms that scales as t o ( 1 ) / ϵ o ( 1 ) for simulation time t and error ϵ . The second approach uses long-time path integrals for near-adiabatic systems and has query complexity that scales as O ( 1 / ϵ ) if the energy eigenvalue gaps and simulation time is sufficiently long. Finally, we show that our Lagrangian simulation algorithm requires a number of queries to an oracle that computes the discrete Lagrangian that scales for a system with η particles in D + 1 dimensions as O ~ ( η D t 2 / ϵ ) if V ( x ) is bounded and finite and the wavefunction obeys appropriate position and momentum cutoffs. This shows that Lagrangian dynamics can be efficiently simulated on quantum computers and opens up the possibility for quantum field theories for which the Hamiltonian is unknown to be efficiently simulated on quantum computers.
We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })