01142nas a2200157 4500008004100000245008300041210006900124260001500193520063900208100002300847700001800870700002400888700001900912700001600931856003700947 2014 eng d00aDifferent Strategies for Optimization Using the Quantum Adiabatic Algorithm
0 aDifferent Strategies for Optimization Using the Quantum Adiabati c2014/01/283 a We present the results of a numerical study, with 20 qubits, of the
performance of the Quantum Adiabatic Algorithm on randomly generated instances
of MAX 2-SAT with a unique assignment that maximizes the number of satisfied
clauses. The probability of obtaining this assignment at the end of the quantum
evolution measures the success of the algorithm. Here we report three
strategies which consistently increase the success probability for the hardest
instances in our ensemble: decreasing the overall evolution time, initializing
the system in excited states, and adding a random local Hamiltonian to the
middle of the evolution.
1 aCrosson, Elizabeth1 aFarhi, Edward1 aLin, Cedric, Yen-Yu1 aLin, Han-Hsuan1 aShor, Peter uhttp://arxiv.org/abs/1401.7320v101446nas a2200157 4500008004100000245003200041210002800073260001500101520104100116100002001157700001801177700002001195700002001215700001601235856003701251 2008 eng d00aThe Power of Unentanglement0 aPower of Unentanglement c2008/04/043 a The class QMA(k), introduced by Kobayashi et al., consists of all languages
that can be verified using k unentangled quantum proofs. Many of the simplest
questions about this class have remained embarrassingly open: for example, can
we give any evidence that k quantum proofs are more powerful than one? Does
QMA(k)=QMA(2) for k>=2? Can QMA(k) protocols be amplified to exponentially
small error? In this paper, we make progress on all of the above questions.
First, we give a protocol by which a verifier can be convinced that a 3SAT
formula of size n is satisfiable, with constant soundness, given ~O(sqrt(n))
unentangled quantum witnesses with O(log n) qubits each. Our protocol relies on
the existence of very short PCPs. Second, we show that assuming a weak version
of the Additivity Conjecture from quantum information theory, any QMA(2)
protocol can be amplified to exponentially small error, and QMA(k)=QMA(2) for
all k>=2. Third, we prove the nonexistence of "perfect disentanglers" for
simulating multiple Merlins with one.
1 aAaronson, Scott1 aBeigi, Salman1 aDrucker, Andrew1 aFefferman, Bill1 aShor, Peter uhttp://arxiv.org/abs/0804.0802v2