Abstract | ||
---|---|---|
Given a verifier circuit for a problem in QMA, we show how to exponentially amplifythe gap between its acceptance probabilities in the 'yes' and 'no' cases, with a methodthat is quadratically faster than the procedure given by Marriott and Watrous [1]. Ourconstruction is natively quantum, based on the analogy of a product of two reflections anda quantum walk. Second, in some special cases we show how to amplify the acceptanceprobability for good witnesses to 1, making a step towards the proof that QMA withone-sided error (QMA1) is equal to QMA. Finally, we simplify the filter-state method tosearch for QMA witnesses by Poulin and Wocjan [2]. |
Year | Venue | Keywords |
---|---|---|
2011 | Quantum Information & Computation | filter-state method tosearch,special case,qma withone-sided error,acceptance probability,good witness,amplifythe gap,verifier circuit,qma witness,fast amplification,natively quantum,quantum physics,quantum walk,jordan s lemma |
Field | DocType | Volume |
Discrete mathematics,Quantum,Quadratic growth,Quantum mechanics,Quantum walk,Analogy,Jordan's lemma,Mathematics | Journal | 9 |
Issue | ISSN | Citations |
11 | QIC Vol.9 No.11&12 (2009), 1053-1068 | 20 |
PageRank | References | Authors |
1.19 | 12 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Daniel Nagaj | 1 | 57 | 5.84 |
Pawel Wocjan | 2 | 136 | 22.21 |
Yong Zhang | 3 | 20 | 1.19 |