@article {1516,
title = {Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
},
year = {2014},
month = {2014/01/28},
abstract = { 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.
},
url = {http://arxiv.org/abs/1401.7320v1},
author = {Elizabeth Crosson and Edward Farhi and Cedric Yen-Yu Lin and Han-Hsuan Lin and Peter Shor}
}
@article {1465,
title = {The Power of Unentanglement},
year = {2008},
month = {2008/04/04},
abstract = { 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.
},
url = {http://arxiv.org/abs/0804.0802v2},
author = {Scott Aaronson and Salman Beigi and Andrew Drucker and Bill Fefferman and Peter Shor}
}