Alireza Goldar, Zhen Qin, Zhihui Zhu et al.
Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance?Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential…
Ruixuan Deng, Zhengfeng Ji, Jiayu Zhang et al.
Quantum key distribution (QKD), whose security is derived from quantum mechanics rather than computational assumptions, is moving into standardization and commercial…Quantum key distribution (QKD), whose security is derived from quantum mechanics rather than computational assumptions, is moving into standardization and commercial deployment.
Liang-Liang Sun, Jie Wang, Sixia Yu
Bell nonlocality places the long-standing philosophical disputes over the nature of quantum theory on a mathematically rigorous, experimentally testable footing…Bell nonlocality places the long-standing philosophical disputes over the nature of quantum theory on a mathematically rigorous, experimentally testable footing, positioning quantum mechanics between local realism and the most…
Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub et al.
In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security…In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries.
Robin Harper, Xanda C. Kolesnikow, Campbell K. McLauchlan et al.
We demonstrate high-fidelity logical qubit operations using ibm_phoenix, a square-lattice array of 120 coupled superconducting qubits that are capable of fast reset.We demonstrate high-fidelity logical qubit operations using ibm_phoenix, a square-lattice array of 120 coupled superconducting qubits that are capable of fast reset.
Mohammed Barhoush, Amit Behera
In classical cryptography, one-way functions are necessary for most of cryptography.In classical cryptography, one-way functions are necessary for most of cryptography.
A proof showed that a cryptographic protocol lets standard machines run private computations and store hidden memory on a remote quantum server.A proof showed that a cryptographic protocol lets standard machines run private computations and store hidden memory on a remote quantum server.
Marcos Crichigno, Steve Flammia
Compiling quantum algorithms for real devices involves hard optimization problems that can decide whether an algorithm runs at scale.Compiling quantum algorithms for real devices involves hard optimization problems that can decide whether an algorithm runs at scale. We present a general method for solving such problems with AI agents, with every result…
Mohammed Barhoush
We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state.We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target.
Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng
A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules…A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules unchanged can protect such accounts: their funds must move into…
Byeongseon Go, Hyunseok Jeong
Understanding how photon loss changes the classical complexity of BosonSampling is central to assessing the robustness of near-term photonic quantum advantage.Understanding how photon loss changes the classical complexity of BosonSampling is central to assessing the robustness of near-term photonic quantum advantage.
Markus Baumann, Jonas Stein, Claudia Linnhoff-Popien
Fresh qubits, not size, set how long a noisy quantum system can remember. With k input qubits reinitialized per time step, the longest memory any reservoir can attain…Fresh qubits, not size, set how long a noisy quantum system can remember. With k input qubits reinitialized per time step, the longest memory any reservoir can attain under depolarizing noise is exp[Θ(k)] time steps, whatever its…
A proof shows that a quantum walker hopping across a two-dimensional grid needs extra steps to find a target, resolving an open question from 2003.A proof shows that a quantum walker hopping across a two-dimensional grid needs extra steps to find a target, resolving an open question from 2003.
Minbo Gao, Tianshi Yu, Lihong Zhi
We construct an explicit binary linear system game that separates Cqa, the closure of the set of finite dimensional quantum correlations, from Cqc, the set of commuting…We construct an explicit binary linear system game that separates Cqa, the closure of the set of finite dimensional quantum correlations, from Cqc, the set of commuting operator correlations.
Furqan Nasir, Sher Jeel Ahmad
Estimates of the quantum resources needed to run fault-tolerant algorithms are almost always reported as single numbers, even though they rest on uncertain hardware…Estimates of the quantum resources needed to run fault-tolerant algorithms are almost always reported as single numbers, even though they rest on uncertain hardware parameters and on cost models that disagree.
Pei Yuan, Wei Zi, Shengyu Zhang
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates.Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates.
Serban Cercelescu, Mark Koch, Arthur Pesah
We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic…We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic Pauli noise.
Alexander Schmidhuber, Alexander Zlokapa
The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics.The Sachdev-Ye-Kitaev model is a strongly interacting fermionic system that has been well-studied in condensed matter and high energy physics.
Keshav Bhateja, Mehdi Esmaili, Atul Mantri
Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores…Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities.
Andrew Huang, Akshar Ramkumar, John Wright
A major open problem in quantum complexity is the question of unitary synthesis—namely, is it possible to efficiently implement any unitary, given the ability to evaluate…A major open problem in quantum complexity is the question of unitary synthesis—namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition?
Chenfeng Cao
Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact n-qubit unitary synthesis from Θ(n) to O(1), using arbitrary one- and…Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact n-qubit unitary synthesis from Θ(n) to O(1), using arbitrary one- and two-qubit gates and unrestricted ancillary space.
Ryan Anselm, Michelle Ding, Dar Gilboa et al.
We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and…We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an n-qubit quantum one-way protocol…
A proof showed that finding or even approaching a local minimum when training variational quantum circuits is computationally hard in the worst case.A proof showed that finding or even approaching a local minimum when training variational quantum circuits is computationally hard in the worst case.
Jiaqing Jiang, Nathan Ju, Ojas Parekh et al.
Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods.Quantum impurity models are paradigmatic models of interacting quantum matter, as well as key computational primitives for modern electronic-structure methods.
Ryan Anselm, Srijita Kundu, Olivier Lalonde et al.
A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement…A longstanding question in quantum communication complexity is whether some task can be accomplished with a small amount of communication in the presence of entanglement, yet require much more quantum communication in the absence…
Kewen Wu, Guangxu Yang
Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025).Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation…
Jon Nelson, Joel Rajakumar, Chao Yin et al.
Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage.Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow…
A preprint proves that quantum circuits need only linear depth for any operation, an exponential improvement on the previous best bound by Rosenthal.A preprint proves that quantum circuits need only linear depth for any operation, an exponential improvement on the previous best bound by Rosenthal.
Amin Shiraz Gilani, Xingyu Zhou
Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H.Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query…
Kishor Bharti, Tobias Haug, Derek Khu et al.
Recent work established that, for independent erasures, storing K logical qubits for S time steps with error at most ε requires a spacetime cost of Ω(S(K+log(S/ε))).Recent work established that, for independent erasures, storing K logical qubits for S time steps with error at most ε requires a spacetime cost of Ω(S(K+log(S/ε))).
Adam Bouland, Matthew Ding, Siddhartha Jain
We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa–Zhandry Code Intersection problem admits exponential…We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa–Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are…
Martino Bernasconi, Giulio Malavolta
We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the k local factors of dimension d is chosen from a convex set.We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the k local factors of dimension d is chosen from a convex set.
Dominic W. Berry, Abhishek Rawat, Sophia Simon et al.
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity.We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity.
Zhili Chen, Rahul Jain, YaoNan Zhang
Assuming post-quantum one-way functions, we construct device-independent (DI) oblivious transfer (OT) and bit commitment: honest parties use only trusted classical…Assuming post-quantum one-way functions, we construct device-independent (DI) oblivious transfer (OT) and bit commitment: honest parties use only trusted classical computation to operate untrusted quantum devices, which may share…
Matthew Coudron, Michael J. Gullans, Jon Nelson et al.
We give a deterministic classical algorithm that estimates |langle x|U|0ⁿrangle|² to additive error ε in poly(n, 1/ε) time, where U is a constant-depth quantum circuit…We give a deterministic classical algorithm that estimates |langle x|U|0ⁿrangle|² to additive error ε in poly(n, 1/ε) time, where U is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary…
Srinivasan Arunachalam, Sergey Bravyi, Anirban Chowdhury et al.
A quantum impurity model describes a small interacting subsystem embedded into a large bath of free fermions.A quantum impurity model describes a small interacting subsystem embedded into a large bath of free fermions. Here we study the computational complexity of calculating the ground energy, thermal equilibrium, and dynamical…
Aniruddha Sen, Nicholas Hunter-Jones
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems.Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems.
L. Bittel, J. Eisert, W. Gong et al.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation.Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation.
Zecheng Li, Chunhao Wang
We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ‖H‖_(1→2).We give a quantum algorithm for simulating a d-sparse Hermitian Hamiltonian H, assuming a known upper bound Λ on its maximum column Euclidean norm ‖H‖_(1→2).
Guang Hao Low
We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices.We develop Multivariate Quantum Signal Processing for designing matrix-valued transformations of multiple noncommuting nonnormal block-encoded matrices.