Simulating LDPC code Hamiltonians on 2D lattices
- URL: http://arxiv.org/abs/2308.13277v1
- Date: Fri, 25 Aug 2023 09:59:47 GMT
- Title: Simulating LDPC code Hamiltonians on 2D lattices
- Authors: Harriet Apel, Nou\'edyn Baspin
- Abstract summary: We build a simulation of LDPC codes using only 2D nearest-neighbour interactions at the cost of an energy penalty in the system size.
We derive guarantees for the simulation that allows us to approximately reproduce the ground state of the code Hamiltonian.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While LDPC codes have been demonstrated with desirable error correcting
properties, this has come at a cost of diverging from the geometrical
constraints of many hardware platforms. Viewing codes as the groundspace of a
Hamiltonian, we consider engineering a simulation Hamiltonian reproducing some
relevant features of the code. Techniques from Hamiltonian simulation theory
are used to build a simulation of LDPC codes using only 2D nearest-neighbour
interactions at the cost of an energy penalty polynomial in the system size. We
derive guarantees for the simulation that allows us to approximately reproduce
the ground state of the code Hamiltonian, approximating a $[[N,
\Omega(\sqrt{N}), \Omega(\sqrt{N})]]$ code in 2D. The key ingredient is a new
constructive tool to simulate an $l$-long interaction between two qubits by a
1D chain of $l$ nearest-neighbour interacting qubits using $\mathrm{poly}( l)$
interaction strengths. This is an exponential advantage over the existing
gadgets for this routine which facilitates the first $\epsilon$-simulation of
\emph{arbitrary sparse} Hamiltonian on $n$ qubits with a Hamiltonian on a 2D
lattice of $O(n^2)$ qubits with interaction strengths scaling as
$O\left(\mathrm{poly}(n,1/\epsilon)\right)$.
Related papers
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators.
Key to our solution is a novel projection technique based on ideas from harmonic analysis.
Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
arXiv Detail & Related papers (2024-05-10T09:58:47Z) - Hamiltonian simulation of minimal holographic sparsified SYK model [0.0]
Hamiltonian simulation of the sparsified SYK model with $N$ Majorana fermions and $q=4$ (quartic interactions)
This complexity implies that with less than a hundred logical qubits and about $106$ gates, it will be possible to achieve an advantage in this model and simulate real-time dynamics up to scrambling time.
arXiv Detail & Related papers (2024-04-23T06:49:34Z) - 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) - Simplifying the simulation of local Hamiltonian dynamics [0.0]
Local Hamiltonians, $H_k$, describe non-trivial $k$-body interactions in quantum many-body systems.
We build upon known methods to derive examples of $H_k$ and $H_k'$ that simulate the same physics.
We propose a method to search for the $k'$-local Hamiltonian that simulates, with the highest possible precision, the short time dynamics of a given $H_k$ Hamiltonian.
arXiv Detail & Related papers (2023-10-10T22:31:45Z) - Composite QDrift-Product Formulas for Quantum and Classical Simulations
in Real and Imaginary Time [0.18374319565577155]
Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian $H$ for a given simulation problem into subsets.
We show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations.
We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form $e-iH_j t$ and $e-H_j beta$ to meet a certain error tolerance.
arXiv Detail & Related papers (2023-06-28T21:31:26Z) - On the Impossibility of General Parallel Fast-forwarding of Hamiltonian
Simulation [4.925967492198012]
Hamiltonian simulation is one of the most important problems in the field of quantum computing.
Existing simulation algorithms require running time at least linear in the evolution time $T$.
It is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism.
arXiv Detail & Related papers (2023-05-21T12:30:00Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis.
We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$.
Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions.
We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$.
We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
arXiv Detail & Related papers (2022-02-23T16:10:23Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings.
In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$.
We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
arXiv Detail & Related papers (2020-02-25T19:18:36Z)
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.