REVIEW 2 cited by
One-Way Ticket to Las Vegas and the Quantum Adversary
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We propose a new definition of quantum Las Vegas query complexity. We show that it is exactly equal to the quantum adversary bound. This is achieved by a new and very simple way of transforming a feasible solution to the adversary optimisation problem into a quantum query algorithm. This allows us to generalise the bound to include unidirectional access, multiple input oracles, and input oracles that are not unitary. As an application, we demonstrate a separation between unidirectional and bidirectional access to an input oracle for a rather natural unitary permutation inversion problem.
Forward citations
Cited by 2 Pith papers
-
Time-Dependent Hamiltonian Simulation with Optimal Query Complexity
For Lipschitz time-dependent Hamiltonians, the new algorithm uses O(alpha T + log(1/epsilon)/log(e + log(1/epsilon)/(alpha T))) HAM-T queries, matching the lower bound for time-independent simulation.
-
Composing Quantum Algorithms
A survey explaining that bounded-error quantum algorithms can be composed without the log factor that classical randomized composition requires, using the transducer model.
Discussion (0). Continue with ORCID to comment.