The detectability lemma and quantum gap amplification. (English) Zbl 1304.68049
Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 417-426 (2009).
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 68Q25 | Analysis of algorithms and problem complexity |
| 81P68 | Quantum computation |
Citations:
Zbl 1292.68074References:
| [1] | D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The Detectability Lemma and Quantum Gap Amplification. arXiv:0811.3412, 2008. |
| [2] | M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in LOGSPACE. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 132-140. ACM New York, NY, USA, 1987. 10.1145/28395.28410 |
| [3] | S. Arora and B. Barak. Computational Complexity: A Modern Approach. to appear: http://www.cs.princeton.edu/theory/complexity. |
| [4] | S. Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. quant-ph/0602108, 2006. |
| [5] | S. Bravyi, D. DiVincenzo, D. Loss, and B. Terhal. Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions. Physical Review Letters, 101(7):70503, 2008. |
| [6] | I. Dinur. The pcp theorem by gap amplification. J. ACM, 54(3):12, 2007. 10.1145/1236457.1236459 · Zbl 1292.68074 |
| [7] | E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106, 2000. |
| [8] | R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 248-253, 1989. 10.1109/SFCS.1989.63486 |
| [9] | S. P. Jordan and E. Farhi. Perturbative gadgets at arbitrary orders. Physical Review A (Atomic, Molecular, and Optical Physics), 77(6):062329, 2008. |
| [10] | J. Kempe, A. Kitaev, and O. Regev. The Complexity of the Local Hamiltonian Problem. SIAM JOURNAL ON COMPUTING, 35(5):1070, 2006. 10.1137/S0097539704445226 · Zbl 1102.81032 |
| [11] | A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. · Zbl 1022.68001 |
| [12] | J. ’Lberg, D. Kult, and E. Sjöqvist. Robustness of the adiabatic quantum search. Physical Review A, 71(6):60312, 2005. |
| [13] | D. A. Lidar. Towards fault tolerant adiabatic quantum computation. Physical Review Letters, 100(16):160506, 2008. |
| [14] | C. Marriott and J. Watrous. Quantum arthur-merlin games. Computational Complexity, 14(2):122-152, 2005. 10.1007/s00037-005-0194-x · Zbl 1085.68052 |
| [15] | R. Oliveira and B. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quant. Inf. Comp., 8(10):0900-0924, 2008. · Zbl 1161.81007 |
| [16] | J. Roland and N. Cerf. Noise resistance of adiabatic quantum computation using random matrix theory. Physical Review A, 71(3):32330, 2005. · Zbl 1227.81126 |
| [17] | M. Sarandy and D. Lidar. Adiabatic Quantum Computation in Open Systems. Physical Review Letters, 95(25):250503, 2005. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
