Title

Fast Amplification Of Qma

Keywords

Amplification; Jordan's lemma; Phase estimation; QMA; Witness-reusing

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

Publication Date

11-1-2009

Publication Title

Quantum Information and Computation

Volume

9

Issue

11-12

Number of Pages

1053-1068

Document Type

Article

Personal Identifier

scopus

Socpus ID

71549143511 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/71549143511

This document is currently not available here.

Share

COinS