Skip to content
TILens What matters today in tech v0.3.2
Theme

Daily edition · Algorithms

The daily ledger

TILens turns technical updates into a focused daily brief: official releases, trusted reporting, and practitioner analysis, deduplicated and organized by topic.

02 Oct 2026 edition

87 articles · 3 sources · 87 papers ·

Top topics: Algorithms · AI

Algorithms

Time-space lower bounds for breaking quantum cryptography

arXiv:2610.02101v1 Announce Type: cross Abstract: We prove near-optimal time-space lower bounds for breaking quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$…

Source: arXiv cs.CC Fangqi Dong, Alex Lombardi
Algorithms

Polynomial-time local-unitary equivalence of graph states

arXiv:2610.00527v1 Announce Type: cross Abstract: Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can…

Source: arXiv cs.CC Yuxuan Zhang
Algorithms

Quantum state isomorphism problems for groups

arXiv:2605.12615v2 Announce Type: replace-cross Abstract: We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states,…

Source: arXiv cs.CC Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban, Arsalan Motamedi
Algorithms

Trapdoored Clifford Operators and Applications

arXiv:2610.01848v1 Announce Type: cross Abstract: Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However,…

Source: arXiv cs.CC Minki Hhan, Hojune Lee
Algorithms

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

arXiv:2610.01639v1 Announce Type: new Abstract: Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807)…

Source: arXiv cs.CC Isaac Rudich, Louis-Martin Rousseau
Algorithms

Beyond Light Cones: State Preparation Complexity in Quantum Spin Glasses

arXiv:2610.02166v1 Announce Type: cross Abstract: We introduce a method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit…

Source: arXiv cs.CC Omar Al-Ghattas, David Gamarnik, Bobak T Kiani
Algorithms

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

arXiv:2610.00525v1 Announce Type: cross Abstract: Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral}…

Source: arXiv cs.CC Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik
Algorithms

A Degree--Size Relation for Resolution over Polynomials

arXiv:2610.00837v1 Announce Type: new Abstract: For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same…

Source: arXiv cs.CC Shuo Pang
Algorithms

Toward a Characterization of Simulation Between Arithmetic Theories

arXiv:2604.27787v4 Announce Type: replace Abstract: We study when a sound arithmetic theory $\mathcal S{\supseteq}S^1_2$ with polynomial-time decidable axioms has polynomial-size proofs of $Con_{\mathcal S{+}\phi}(n)$…

Source: arXiv cs.CC Hunter Monroe
Algorithms

Noisy Quantum Query Complexity via Fractional Block Sensitivity

arXiv:2610.00506v1 Announce Type: cross Abstract: We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block…

Source: arXiv cs.CC Mehil Agarwal, Shravas Rao, Fang Song
Algorithms

Optimal transducers using symmetries

arXiv:2610.02133v1 Announce Type: cross Abstract: Transducers (Belovs, Jeffery and Yolcu, 2024) are a quantum computing framework describing a quantum algorithm as a unitary converting an input state into a target state…

Source: arXiv cs.CC Beno\^it Dubus, Julien Ladeuze, J\'er\'emie Roland
Algorithms

The Quantumly Fast and the Classically Forrious

arXiv:2602.07503v2 Announce Type: replace Abstract: We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\operatorname{forr}(f,g)=1$…

Source: arXiv cs.CC Cl\'ement L. Canonne, Kenny Chen, Juli\'an Mestre
Algorithms

The Robustness of QAC0

arXiv:2610.02154v1 Announce Type: cross Abstract: In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero…

Source: arXiv cs.CC Daniel Grier, Jackson Morris, Kewen Wu
Algorithms

Planted Cliques and Quantum Symmetry-Adapted Measurements

arXiv:2609.40310v2 Announce Type: replace-cross Abstract: The planted clique problem is a promising candidate for quantum advantage with a wide computational-statistical gap and substantial evidence for classical…

Source: arXiv cs.CC Vojtech Havlicek, Jordan Docter, Subhash Khot
Algorithms

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

arXiv:2610.00081v1 Announce Type: new Abstract: We prove a complexity dichotomy for Boolean Holant problems defined by arbitrary finite sets of algebraic complex-valued signatures. The tractable cases are characterized…

Source: arXiv cs.CC Chenghua Liu, Boning Meng, Juqiu Wang
Algorithms

Quantum space-depth tradeoffs for coherent block encodings

arXiv:2607.01843v2 Announce Type: cross Abstract: Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require…

Source: arXiv cs.CC Yuxin Zhang, Changpeng Shao

Showing 1 day · 87 items available