Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information security and cryptography

Inapproximability Results for Computational Problems on Lattices

Subhash Khot

Published Jan 1, 2009• 21 citations
Publisher
DOI
10.1007/978-3-642-02295-1_14

Related papers

Chapter 14 Inapproximability Results for Computational Problems on Lattices

Subhash Khot

In this article, we present a survey of known inapproximability results for computational problems on lattices, viz. the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), the Closest Vector Problem with Preprocessing (CVPP), the Covering Radius Problem (CRP), the Shortest Independent Vectors Problem (SIVP), and the Shortest Basis Problem (SBP).

•Jan 1, 2010•0 citations

Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

Louay Bazzi, Georges Khater

Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

quant-pharXiv:2608.17109•Aug 19, 2026•1 citation

Generating Hard Instances of Lattice Problems

Miklós Ajtai

Electronic colloquium on computational complexity•Jan 1, 1996•598 citations

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern +1 more

Journal of Computer and System Sciences•Apr 1, 1997•362 citations

Decidability in Orthomodular Lattices

Marek Hyčko, Mirko Navara

International Journal of Theoretical Physics•Dec 1, 2005•7 citations

A Quantum Unique Games Conjecture

Hamoon Mousavi, Taro Spirig

After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.

arXiv:2409.20028•Leibniz international proceedings in informatics•Sep 30, 2024•6 citations
Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the XXX- and ZZZ-syndromes. For color codes under independent XXX- and ZZZ-error models, we consider Separate Minimum-Weight decoding. Assuming P≠NPP\neq NPP=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the 4.8.84.8.84.8.8 color code on the torus, there exists a constant c>0c>0c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within cN1/14cN^{1/14}cN1/14 of the optimum, where NNN is the number of qubits, unless P=NPP=NPP=NP. For the planar surface code, we obtain an Ω(N1/18)Ω(N^{1/18})Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.