Exponentially faster implementations of Select(H) for fermionic
Hamiltonians
- URL: http://arxiv.org/abs/2004.04170v3
- Date: Thu, 7 Jan 2021 06:33:33 GMT
- Title: Exponentially faster implementations of Select(H) for fermionic
Hamiltonians
- Authors: Kianna Wan
- Abstract summary: We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell.
$textSelect(H)$ is one of the main subroutines of several quantum algorithms.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a simple but general framework for constructing quantum circuits
that implement the multiply-controlled unitary $\text{Select}(H) \equiv
\sum_\ell |\ell\rangle\langle\ell|\otimes H_\ell$, where $H = \sum_\ell H_\ell$
is the Jordan-Wigner transform of an arbitrary second-quantised fermionic
Hamiltonian. $\text{Select}(H)$ is one of the main subroutines of several
quantum algorithms, including state-of-the-art techniques for Hamiltonian
simulation. If each term in the second-quantised Hamiltonian involves at most
$k$ spin-orbitals and $k$ is a constant independent of the total number of
spin-orbitals $n$ (as is the case for the majority of quantum chemistry and
condensed matter models considered in the literature, for which $k$ is
typically 2 or 4), our implementation of $\text{Select}(H)$ requires no ancilla
qubits and uses $\mathcal{O}(n)$ Clifford+T gates, with the Clifford gates
applied in $\mathcal{O}(\log^2 n)$ layers and the $T$ gates in $O(\log n)$
layers. This achieves an exponential improvement in both Clifford- and T-depth
over previous work, while maintaining linear gate count and reducing the number
of ancillae to zero.
Related papers
- Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace.
We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
arXiv Detail & Related papers (2024-04-04T17:58:01Z) - A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
We give a quantum algorithm for solving the ground states of a class of Hamiltonians.
The mechanism of the exponential speedup that appeared in our algorithm comes from dissipation in open quantum systems.
arXiv Detail & Related papers (2024-01-25T05:01:02Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Systematics of quasi-Hermitian representations of non-Hermitian quantum
models [0.0]
This paper introduces and describes a set of constructive returns of the description to one of the correct and eligible physical Hilbert spaces $cal R_N(0)$.
In the extreme of the theory the construction is currently well known and involves solely the inner product metric $Theta=Theta(H)$.
At $j=N$ the inner-product metric remains trivial and only the Hamiltonian must be Hermitized, $H to mathfrakh = Omega,H,Omega-1=mathfrak
arXiv Detail & Related papers (2022-12-07T20:10:58Z) - On the complexity of implementing Trotter steps [2.1369834525800138]
We develop methods to perform faster Trotter steps with complexity sublinear in number of terms.
We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.
Our result suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter synthesis steps with lower gate complexity.
arXiv Detail & Related papers (2022-11-16T19:00:01Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - On quantum algorithms for the Schr\"odinger equation in the
semi-classical regime [27.175719898694073]
We consider Schr"odinger's equation in the semi-classical regime.
Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
arXiv Detail & Related papers (2021-12-25T20:01:54Z) - Anharmonic oscillator: a solution [77.34726150561087]
The dynamics in $x$-space and in $(gx)-space corresponds to the same energy spectrum with effective coupling constant $hbar g2$.
A 2-classical generalization leads to a uniform approximation of the wavefunction in $x$-space with unprecedented accuracy.
arXiv Detail & Related papers (2020-11-29T22:13:08Z)
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.