56 citations · 56 across the 2 of their papers we have counts for
5 papers · 1 filter
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…