The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
Fast Amplification of QMA
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is quadratically faster than the procedure given by Marriott and Watrous. Our construction is natively quantum, based on the analogy of a product of two reflections and a quantum walk. Second, in some special cases we show how to amplify the acceptance probability for good witnesses to 1, making a step towards the proof that QMA with one-sided error is equal to QMA. Finally, we simplify the filter-state method to search for QMA witnesses by Poulin and Wocjan.
fields
quant-ph 2representative citing papers
Resource estimates for quantum simulation of pionless and pionful nuclear lattice EFTs, including time evolution and energy estimation, with new error bounds from symmetries and locality yielding orders-of-magnitude improvements for the pionless case.
citing papers explorer
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Quantum Algorithms for Simulating Nuclear Effective Field Theories
Resource estimates for quantum simulation of pionless and pionful nuclear lattice EFTs, including time evolution and energy estimation, with new error bounds from symmetries and locality yielding orders-of-magnitude improvements for the pionless case.