Impossibility of a quantum speed-up with a faulty oracle

被引：0
|
作者：
Regev, Oded [1 ]
Schiff, Liron [1 ]
机构：
[1] Tel Aviv Univ, Sch Comp Sci, IL-69978 Tel Aviv, Israel
来源：
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS | 2008年 / 5125卷
关键词：
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this case.
引用
收藏
页码：773 / 781
页数：9
相关论文
共 50 条
  • [1] Theory of the quantum speed-up
    Castagnoli, G
    Finkelstein, DR
    PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2001, 457 (2012): : 1799 - 1806
  • [2] Mechanism Of The Quantum Speed-up
    Castagnoli, Giuseppe
    QUANTUM RETROCAUSATION: THEORY AND EXPERIMENT, 2011, 1408 : 99 - 119
  • [3] Quantum speed-up of computations
    Pitowsky, I
    PHILOSOPHY OF SCIENCE, 2002, 69 (03) : S168 - S177
  • [4] Quantum speed-up for unsupervised learning
    Esma Aïmeur
    Gilles Brassard
    Sébastien Gambs
    Machine Learning, 2013, 90 : 261 - 287
  • [5] Quantum speed-up for unsupervised learning
    Aimeur, Esma
    Brassard, Gilles
    Gambs, Sebastien
    MACHINE LEARNING, 2013, 90 (02) : 261 - 287
  • [6] Speed-up and entanglement in quantum searching
    Braunstein, SL
    Pati, AK
    QUANTUM INFORMATION & COMPUTATION, 2002, 2 (05) : 399 - 409
  • [7] Quantum speed-up? Not so fast
    Aron, Jacob
    NEW SCIENTIST, 2015, 228 (3052) : 12 - 12
  • [8] Quantum Speed-Up in Collisional Battery Charging
    Seah, Stella
    Perarnau-Llobet, Marti
    Haack, Geraldine
    Brunner, Nicolas
    Nimmrichter, Stefan
    PHYSICAL REVIEW LETTERS, 2021, 127 (10)
  • [9] Problems and prospects for quantum computational speed-up
    Krishnamurthy, EV
    COMPUTATIONAL SCIENCE - ICCS 2003, PT IV, PROCEEDINGS, 2003, 2660 : 779 - 788
  • [10] On the role of entanglement in quantum-computational speed-up
    Jozsa, R
    Linden, N
    PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 2003, 459 (2036): : 2011 - 2032
12345