56 citations · 56 across the 2 of their papers we have counts for
7 papers
The power of constant-depth quantum circuits of unbounded size
Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit siz…
Fast Cliffords When Your Quantum Memory Is Full
Marten Folkertsma, Ian Mertz, Sergii Strelchuk +1
Additional qubits can reduce the depth of a quantum circuit by providing workspace for parallel computation, but standard constructions assume that this workspace is initialized in…
Complex Quantum Dynamics Versus Classical Simulability of Noisy Random Circuits
Anjali Waghmare, Sergii Strelchuk, Sathyawageeswar Subramanian
Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits…
Average-case hardness of Betti number estimation
Sergii Strelchuk, Sathyawageeswar Subramanian, Adam Wesołowski
We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction imp…
RotorMap and Quantum Fingerprints of DNA Sequences via Rotary Position Embeddings
Danylo Yakymenko, Maksym Chernyshev, Illia Savchenko +1
For strings of letters from a small alphabet, such as DNA sequences, we present a quantum encoding that empirically provides a strong correlation between the Levenshtein edit dista…
Quantum Catalytic Space
Harry Buhrman, Marten Folkertsma, Ian Mertz +4
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation…
Quantum communication complexity advantage implies violation of a Bell inequality
Harry Buhrman, Lukasz Czekaj, Andrzej Grudka +5
We obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum adv…