Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHamiltonian simulation with nearly optimal dependence on spectral norm
131
0
0.0
(
0
)
Authors
Guang Hao Low
Ask ChatGPT about the research
No Arabic abstract
We present a quantum algorithm for approximating the real time evolution $e^{-iHt}$ of an arbitrary $d$-sparse Hamiltonian to error $epsilon$, given black-box access to the positions and $b$-bit values of its non-zero matrix entries. The complexity of our algorithm is $mathcal{O}((tsqrt{d}|H|_{1 rightarrow 2})^{1+o(1)}/epsilon^{o(1)})$ queries and a factor $mathcal{O}(b)$ more gates, which is shown to be optimal up to subpolynomial factors through a matching query lower bound. This provides a polynomial speedup in sparsity for the common case where the spectral norm $|H|ge|H|_{1 rightarrow 2}$ is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem -- $mathcal{O}(d^{1/2+o(1)})$ queries suffice to approximate any $d$-sparse unitary in the black-box setting, which matches the quantum search lower bound of $Omega(sqrt{d})$ queries and improves upon prior art [Berry and Childs, QIP 2010] of $tilde{mathcal{O}}(d^{2/3})$ queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number $kappa$ using $mathcal{O}((kappa sqrt{d})^{1+o(1)}/epsilon^{o(1)})$ queries, which is a quadratic improvement in sparsity.
rate research
Read More
The accuracy of quantum dynamics simulation is usually measured by the error of the unitary evolution operator in the operator norm, which in turn depends on certain norm of the Hamiltonian. For unbounded operators, after suitable discretization, the norm of the Hamiltonian can be very large, which significantly increases the simulation cost. However, the operator norm measures the worst-case error of the quantum simulation, while practical simulation concerns the error with respect to a given initial vector at hand. We demonstrate that under suitable assumptions of the Hamiltonian and the initial vector, if the error is measured in terms of the vector norm, the computational cost may not increase at all as the norm of the Hamiltonian increases using Trotter type methods. In this sense, our result outperforms all previous error bounds in the quantum simulation literature. Our result extends that of [Jahnke, Lubich, BIT Numer. Math. 2000] to the time-dependent setting. We also clarify the existence and the importance of commutator scalings of Trotter and generalized Trotter methods for time-dependent Hamiltonian simulations.
The numerical emulation of quantum physics and quantum chemistry often involves an intractable number of degrees of freedom and admits no known approximation in general form. In practice, representing quantum-mechanical states using available numerical methods becomes exponentially more challenging with increasing system size. Recently quantum algorithms implemented as variational models, have been proposed to accelerate such simulations. Here we study the effect of noise on the quantum phase transition in the Schwinger model, within a variational framework. The experiments are built using a free space optical scheme to realize a pair of polarization qubits and enable any two-qubit state to be experimentally prepared up to machine tolerance. We specifically exploit the possibility to engineer noise and decoherence for polarization qubits to explore the limits of variational algorithms for NISQ architectures in identifying and quantifying quantum phase transitions with noisy qubits. We find that despite the presence of noise one can detect the phase transition of the Schwinger Hamiltonian even for a two-qubit system using variational quantum algorithms.
Product formula approximations of the time-evolution operator on quantum computers are of great interest due to their simplicity, and good scaling with system size by exploiting commutativity between Hamiltonian terms. However, product formulas exhibit poor scaling with the time $t$ and error $epsilon$ of simulation as the gate cost of a single step scales exponentially with the order $m$ of accuracy. We introduce well-conditioned multiproduct formulas, which are a linear combination of product formulas, where a single step has polynomial cost $mathcal{O}(m^2log{(m)})$ and succeeds with probability $Omega(1/operatorname{log}^2{(m)})$. Our multiproduct formulas imply a simple and generic simulation algorithm that simultaneously exploits commutativity in arbitrary systems and has a worst-case cost $mathcal{O}(tlog^{2}{(t/epsilon)})$ which is optimal up to poly-logarithmic factors. In contrast, prior Trotter and post-Trotter Hamiltonian simulation algorithms realize only one of these two desirable features. A key technical result of independent interest is our solution to a conditioning problem in previous multiproduct formulas that amplified numerical errors by $e^{Omega(m)}$ in the classical setting, and led to a vanishing success probability $e^{-Omega(m)}$ in the quantum setting.
Quantum computing can efficiently simulate Hamiltonian dynamics of many-body quantum physics, a task that is generally intractable with classical computers. The hardness lies at the ubiquitous anti-commutative relations of quantum operators, in corresponding with the notorious negative sign problem in classical simulation. Intuitively, Hamiltonians with more commutative terms are also easier to simulate on a quantum computer, and anti-commutative relations generally cause more errors, such as in the product formula method. Here, we theoretically explore the role of anti-commutative relation in Hamiltonian simulation. We find that, contrary to our intuition, anti-commutative relations could also reduce the hardness of Hamiltonian simulation. Specifically, Hamiltonians with mutually anti-commutative terms are easy to simulate, as what happens with ones consisting of mutually commutative terms. Such a property is further utilized to reduce the algorithmic error or the gate complexity in the truncated Taylor series quantum algorithm for general problems. Moreover, we propose two modified linear combinations of unitaries methods tailored for Hamiltonians with different degrees of anti-commutation. We numerically verify that the proposed methods exploiting anti-commutative relations could significantly improve the simulation accuracy of electronic Hamiltonians. Our work sheds light on the roles of commutative and anti-commutative relations in simulating quantum systems.
Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multi-qubit control gates. We propose a drastically simplified quantum circuit called the minimal QSVT circuit, which uses only one ancilla qubit to simulate a class of $n$-qubit random Hamiltonians. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. We demonstrate that QUES is directly related to the circuit fidelity, and the classical hardness of an associated quantum circuit sampling problem. Theoretical analysis suggests under suitable assumptions, there exists an optimal simulation time $t^{text{opt}}approx 4.81$, at which even a noisy quantum device may be sufficient to demonstrate the classical hardness.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
