Fast Amplification of QMA - Quantum PhysicsReportar como inadecuado

Fast Amplification of QMA - Quantum Physics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Given a verifier circuit for a problem in QMA, we show how to exponentiallyamplify the gap between its acceptance probabilities in the `yes- and `no-cases, with a method that is quadratically faster than the procedure given byMarriott and Watrous. Our construction is natively quantum, based on theanalogy of a product of two reflections and a quantum walk. Second, in somespecial cases we show how to amplify the acceptance probability for goodwitnesses to 1, making a step towards the proof that QMA with one-sided erroris equal to QMA. Finally, we simplify the filter-state method to search for QMAwitnesses by Poulin and Wocjan.

Autor: Daniel Nagaj, Pawel Wocjan, Yong Zhang


Documentos relacionados