Title

FAST AMPLIFICATION OF QMA

Authors

Authors

D. Nagaj; P. Wocjan;Y. Zhang

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Quantum Inform. Comput.

Keywords

QMA; amplification; witness-reusing; phase estimation; Jordan's lemma; Computer Science, Theory & Methods; Physics, Particles & Fields; Physics, Mathematical

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 [1]. 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 (QMA(1)) is equal to QMA. Finally, we simplify the filter-state method to search for QMA witnesses by Poulin and Wocian [2].

Journal Title

Quantum Information & Computation

Volume

9

Issue/Number

11-12

Publication Date

1-1-2009

Document Type

Article

Language

English

First Page

1053

Last Page

1068

WOS Identifier

WOS:000273154600008

ISSN

1533-7146

Share

COinS