53 citations · 92 across the 14 of their papers we have counts for
17 papers
An Efficient Quantum Decoder for Prime-Power Fields
Lior Eldar
We consider a version of the nearest-codeword problem on finite fields using the Manhattan distance, an analog of the Hamming metric for non-binary alphabets. Simila…
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
Lior Eldar, Sean Hallgren
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The quantum algorithm…
Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
Enric Boix-Adserà, Lior Eldar, Saeed Mehraban
The determinant can be computed by classical circuits of depth , and therefore it can also be computed in classical space . Recent progress by Ta-Shma [Ta…
Robust Quantum Entanglement at (nearly) Room Temperature
Lior Eldar
We formulate a mixed-state analog of the NLTS conjecture [FH14] by asking whether there exist topologically-ordered systems for which the thermal Gibbs state for constant temperatu…
Approximating the Permanent of a Random Matrix with Vanishing Mean
Lior Eldar, Saeed Mehraban
We show an algorithm for computing the permanent of a random matrix with vanishing mean in quasi-polynomial time. Among special cases are the Gaussian, and biased-Bernoulli random…
A Discrete Fourier Transform on Lattices with Quantum Applications
Lior Eldar, Peter Shor
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in , that generalizes the -th fold DFT of the integer lattice …
An Efficient Quantum Algorithm for a Variant of the Closest Lattice-Vector Problem
Lior Eldar, Peter W. Shor
The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor '16], in which the basis entries satisfy a certain co-primality condition. Using a "smo…
The Need for Structure in Quantum LDPC Codes
Lior Eldar, Maris Ozols, Kevin F. Thompson
Existence of quantum low-density parity-check (LDPC) codes whose minimal distance scales linearly with the number of qubits is a major open problem in quantum information. Its prac…
The Systematic Normal Form of Lattices
Lior Eldar, Peter W. Shor
We introduce a new canonical form of lattices called the systematic normal form (SNF). We show that for every lattice there is an efficiently computable "nearby" SNF lattice, such…
Local Hamiltonians Whose Ground States are Hard to Approximate
Lior Eldar, Aram W. Harrow
Ground states of local Hamiltonians can be generally highly entangled: any quantum circuit that generates them (even approximately) must be sufficiently deep to allow coupling (ent…
A Quasi-Random Approach to Matrix Spectral Analysis
Michael Ben-Or, Lior Eldar
Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorith…
Local Hamiltonians with Approximation-Robust Entanglement
Lior Eldar
Quantum entanglement is considered, by and large, to be a very delicate and non-robust phenomenon that is very hard to maintain in the presence of noise, or non-zero temperatures.…
Optimal algorithms for linear algebra by quantum inspiration
Michael Ben-Or, Lior Eldar
Recent results by Harrow et. al. and by Ta-Shma, suggest that quantum computers may have an exponential advantage in solving a wealth of linear algebraic problems, over classical a…
The commuting local Hamiltonian on locally-expanding graphs is in NP
Dorit Aharonov, Lior Eldar
The local Hamiltonian problem is famously complete for the class QMA, the quantum analogue of NP. The complexity of its semi-classical version, in which the terms of the Hamiltonia…
Quantum Locally Testable Codes
Dorit Aharonov, Lior Eldar
We initiate the study of quantum Locally Testable Codes (qLTCs). We provide a definition together with a simplification, denoted sLTCs, for the special case of stabilizer codes, to…
Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture
Dorit Aharonov, Lior Eldar
Understanding commuting local Hamiltonians (CLHs) is at the heart of many questions in quantum computational complexity and quantum physics: quantum error correcting codes, quantum…
On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
Dorit Aharonov, Lior Eldar
The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quan…