Compare Papers
Paper 1
On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang
- Year
- 2024
- Journal
- arXiv preprint
- DOI
- arXiv:2411.04124
- arXiv
- 2411.04124
We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the gap $\mathrm{Max}$-$\mathrm{Cut}$ problem) to $γ\text{-}\mathrm{CVP}_p$ for $γ= \mathrm{O}(1)$ and finite $p\geq 1$, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from $k$-SAT to $\mathrm{CVP}_2$. This implies three headline results: (i) Faster algorithms for $γ\text{-}\mathrm{CVP}$ are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a $2^{0.78n}$-time or $2^{0.3n}$-time algorithm would improve upon the state-of-the-art algorithm such as Williams' 2004 algorithm [Theoretical Computer Science 2005] or Arora et al.'s 2010 algorithm [Journal of the ACM 2015]. This provides evidence that $γ\text{-}\mathrm{CVP}$ for $γ=\mathrm{O}(1)$ requires exponential time, improving upon the previous lower-bound for $γ<3$ by Bennett et al. [arxiv:1704.03928]. (ii) A new almost $2^{(1/2+\varepsilon/4ς+o(1))n}$-time classical algorithm and a new almost $2^{(1/3+\varepsilon/6ς+o(1))n}$-time quantum algorithm for $(1-\varepsilon,1-ς)$-gap Max-2-Lin(2). This algorithm is faster than the algorithm of Arora et al., as well as the algorithm of Williams, and the algorithm of Manurangsi and Trevisan [arxiv:1807.09898] when $c_0 \varepsilon<ς<c_1 \varepsilon$ for some constants $c_0, c_1$. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a $2^{δn}$-time lower-bound for Max-Cut, Max-2-Lin(2), or $\mathrm{CVP}_2$ for any constant $δ>0$, it must be via an adaptive quantum reduction unless $\mathrm{NP} \subseteq \mathrm{pr}\text{-}\mathrm{QSZK}$. This illuminates some difficulties in characterizing the hardness of approximate CSPs and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH.
Open paperPaper 2
Qubit-oscillator concatenated codes: decoding formalism & code comparison
Yijia Xu, Yixu Wang, En-Jui Kuo, Victor V. Albert
- Year
- 2022
- Journal
- arXiv preprint
- DOI
- arXiv:2209.04573
- arXiv
- 2209.04573
Concatenating bosonic error-correcting codes with qubit codes can substantially boost the error-correcting power of the original qubit codes. It is not clear how to concatenate optimally, given there are several bosonic codes and concatenation schemes to choose from, including the recently discovered GKP-stabilizer codes [Phys. Rev. Lett. 125, 080503 (2020)}] that allow protection of a logical bosonic mode from fluctuations of the mode's conjugate variables. We develop efficient maximum-likelihood decoders for and analyze the performance of three different concatenations of codes taken from the following set: qubit stabilizer codes, analog/Gaussian stabilizer codes, GKP codes, and GKP-stabilizer codes. We benchmark decoder performance against additive Gaussian white noise, corroborating our numerics with analytical calculations. We observe that the concatenation involving GKP-stabilizer codes outperforms the more conventional concatenation of a qubit stabilizer code with a GKP code in some cases. We also propose a GKP-stabilizer code that suppresses fluctuations in both conjugate variables without extra quadrature squeezing, and formulate qudit versions of GKP-stabilizer codes.
Open paper