Hamiltonian sparsification and gap-simulation

DOI10.4230/LIPICS.ITCS.2019.2MaRDI QIDQ5090371zbMATH OpenFDO

Authors Dorit Aharonov, Leo Zhou

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1804.11084

zbMATH Keywords

quantum Hamiltonian complexityquantum PCPquantum simulationsparsification

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Limitations on the simulation of non-sparse Hamiltonians
• Simulating Sparse Hamiltonians with Star Decompositions
• On the gap of Hamiltonians for the adiabatic simulation of quantum circuits

Cites work

• A note about a partial no-go theorem for quantum PCP
• Coherence in Spontaneous Radiation Processes
• Commutative version of the local Hamiltonian problem and common eigenspace problem
• Fault-tolerant quantum computation by anyons
• Graph sparsification by effective resistances
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• scientific article; zbMATH DE number 1559533 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
• Product-state approximations to quantum states
• Quantum phase transitions
• Resilient quantum computation: error models and thresholds
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Sparse sums of positive semidefinite matrices
• Spectral gap and exponential decay of correlations
• Spectral sparsification of graphs
• Strong converse for identification via quantum channels
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• The complexity of quantum spin systems on a two-dimensional square lattice
• The Complexity of the Local Hamiltonian Problem
• The PCP theorem by gap amplification
• Twice-Ramanujan sparsifiers
• Universal Quantum Simulators

Cited in

(6)

• Translationally invariant universal quantum Hamiltonians in 1D
• Toy models of holographic duality between local Hamiltonians
• Simulating Sparse Hamiltonians with Star Decompositions
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Hamiltonian complexity in the thermodynamic limit

This page was built for publication: Hamiltonian sparsification and gap-simulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090371)