49 citations · 138 across the 16 of their papers we have counts for
23 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…
The Generalized Semi-Clifford Conjecture Holds at Level 4
Maxwell Marcus, Sathyawageeswar Subramanian, Marcel Dall'Agnol
The Clifford hierarchy was introduced by Gottesman and Chuang (arXiv:quant-ph/9908010) to characterize gates that admit fault-tol…
Generating random unitaries by products of conjugated Hamiltonian evolutions
Oscar Scholin, Apollonas S. Matsoukas-Roubeas, Sathyawageeswar Subramanian
Random unitary operations are a fundamental resource for quantum information processing, yet provably generating them with experimentally available controls remains challenging. Ex…
Learning quantum symmetries
Isaac Holt, Sathyawageeswar Subramanian
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we st…
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…
Worst-case depth hierarchy for shallow quantum circuits
Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth…
Unconditional Pseudorandomness against Shallow Quantum Circuits
Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan
Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known con…
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 Channel Testing in Average-Case Distance
Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian +2
We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}…
Unconditionally separating noisy from bounded polynomial threshold circuits of constant depth
Min-Hsiu Hsieh, Leandro Mendes, Michael de Oliveira +1
The rapid evolution of quantum devices fuels concerted efforts to experimentally establish quantum advantage over classical computing. Many demonstrations of quantum advantage, how…
Information-theoretic generalization bounds for learning from quantum data
Matthias Caro, Tom Gur, Cambyse Rouzé +2
Learning tasks play an increasingly prominent role in quantum information and computation. They range from fundamental problems such as state discrimination and metrology over the…
A remark on the quantum complexity of the Kronecker coefficients
Christian Ikenmeyer, Sathyawageeswar Subramanian
We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP. This improves a recent result of Bravyi, Chowdhury, Go…
Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation
Hayata Yamasaki, Sathyawageeswar Subramanian, Satoshi Hayakawa +1
A significant challenge in the field of quantum machine learning (QML) is to establish applications of quantum computation to accelerate common tasks in machine learning such as th…
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur +2
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quan…
Constant-time one-shot testing of large-scale graph states
Hayata Yamasaki, Sathyawageeswar Subramanian
Fault-tolerant measurement-based quantum computation (MBQC) with recent progress on quantum technologies leads to a promising scalable platform for realizing quantum computation, c…
Sublinear quantum algorithms for estimating von Neumann entropy
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
Entropy is a fundamental property of both classical and quantum systems, spanning myriad theoretical and practical applications in physics and computer science. We study the proble…
Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions
Hayata Yamasaki, Sathyawageeswar Subramanian, Sho Sonoda +1
Kernel methods augmented with random features give scalable algorithms for learning from big data. But it has been computationally hard to sample random features according to a pro…
Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
Steven Herbert, Sathyawageeswar Subramanian
We study the potential utility of classical techniques of spectral sparsification of graphs as a preprocessing step for digital quantum algorithms, in particular, for Hamiltonian s…
A Quantum Search Decoder for Natural Language Processing
Johannes Bausch, Sathyawageeswar Subramanian, Stephen Piddock
Probabilistic language models, e.g. those based on an LSTM, often face the problem of finding a high probability prediction from a sequence of random variables over a set of tokens…
Quantum algorithm for estimating Renyi entropies of quantum states
Sathyawageeswar Subramanian, Min-Hsiu Hsieh
We describe a quantum algorithm to estimate the -Renyi entropy of an unknown density matrix for by combining the recent technique of quan…
Implementing smooth functions of a Hermitian matrix on a quantum computer
Sathyawageeswar Subramanian, Steve Brierley, Richard Jozsa
We review existing methods for implementing smooth functions f(A) of a sparse Hermitian matrix A on a quantum computer, and analyse a further combination of these techniques which…