3 papers
quant-ph2026
Measurement Geometry for Quantum Random Access Codes: Beyond Nayak Bound and Toward Optimality
Seiseki Akibue, Rudy Raymond, Suguru Tamaki +1
Quantum random access codes (QRACs) ask how well N classical bits can be encoded into M qubits while allowing any single bit to be recovered. Although the Nayak bound remains the s…
quant-ph2026
Dequantizing Short-Path Quantum Algorithms
François Le Gall, Suguru Tamaki
The short-path quantum algorithm introduced by Hastings (Quantum 2018, 2019) is a variant of adiabatic quantum algorithms that enables an easier worst-case analysis by avoiding the…
cs.DS2025
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Sevag Gharibian, Zeph Landau +3
We present an extremely simple polynomial-space exponential-time -approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomia…