1 citations · 2 across the 4 of their papers we have counts for
6 papers
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}…
Efficient Quantum State Synthesis with One Query
Gregory Rosenthal
We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state there exists a choice of oracle…
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Gregory Rosenthal
We prove that any -qubit unitary can be implemented (i) approximately in time with query access to an appropriate classical oracle, and also (ii) exa…
Interactive Proofs for Synthesizing Quantum States and Unitaries
Gregory Rosenthal, Henry Yuen
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense…
Bounds on the QAC Complexity of Approximating Parity
Gregory Rosenthal
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC circuits are QAC circuits of constant depth, and are quantum analogues of AC$^0…
Beating Treewidth for Average-Case Subgraph Isomorphism
Gregory Rosenthal
For any fixed graph , the subgraph isomorphism problem asks whether an -vertex input graph has a subgraph isomorphic to . A well-known algorithm of Alon, Yuster and Zwick…