Quantum complexity theory

Bernstein, Ethan, Vazirani, Umesh·1993·Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93
DOI 10.1145/167088.167097

Cited by (1,000)

Items 101–200 of 1,000

  1. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
    Sean Hallgren · 2007 · Journal of the ACM
  2. Succinct quantum proofs for properties of finite groups
    John Watrous · 2002 · Annual Symposium on Foundations of Computer Science
  3. Quantum computation of Fourier transforms over symmetric groups
    Robert Beals · 1997 · ACM Symposium on Theory of Computing (STOC)
  4. Monotones and Invariants for Multi-particle Quantum States
    Howard Barnum, Noah Linden · 2001 · Explore Bristol Research
  5. Quantum Search on Bounded-Error Inputs
    Peter Høyer, Michele Mosca, Ronald de Wolf · 2003 · Lecture notes in computer science
  6. High-efficiency single-photon source above the loss-tolerant threshold for efficient linear optical quantum computing
    Xing Ding, Yong-Peng Guo, Mo-Chi Xu, Runze Liu, Geng-Yan Zou, Jun-Yi Zhao, Zhen-Xuan Ge, Qi-Hang Zhang, Hua-Liang Liu, Lin-Jun Wang et al. · 2025 · Nature Photonics
  7. Quantum Entanglement and the Communication Complexity of the Inner Product Function
    Cleve, Richard, van Dam, Wim, Nielsen, Michael, Tapp, Alain · 1999 · Lecture Notes in Computer Science
  8. A polynomial quantum algorithm for approximating the Jones polynomial
    Dorit Aharonov, Vaughan F. R. Jones, Zeph A. Landau · 2006 · ACM Symposium on Theory of Computing (STOC)
  9. Dense quantum coding and a lower bound for 1-way quantum automata
    Andris Ambainis, Ashwin Nayak, Amnon Ta‐Shma, Umesh V. Vazirani · 1999 · ACM Symposium on Theory of Computing (STOC)
  10. Full-state quantum circuit simulation by using data compression
    Xin-Chuan Wu, Sheng Di, Emma Maitreyee Dasgupta, Franck Cappello, Hal Finkel, Yuri Alexeev, Frederic T. Chong · 2019 · International Conference for High Performance Computing, Networking, Storage and Analysis (SC)
  11. Benchmarking Quantum Computers and the Impact of Quantum Noise
    Salonik Resch, Ulya R. Karpuzcu · 2021 · ACM Computing Surveys
  12. Polynomial time algorithms for discrete logarithms and factoring on a quantum computer
    Peter W. Shor · 1994 · Lecture notes in computer science
  13. Quantum computation, quantum theory and AI
    Mingsheng Ying · 2009 · Artificial Intelligence
  14. Full-stack, real-system quantum computer studies: architectural comparisons and design insights
    Murali, Prakash, Linke, Norbert Matthias, Martonosi, Margaret, Abhari, Ali Javadi, Nguyen, Nhung Hong, Alderete, Cinthia Huerta · 2019 · Proceedings of the 46th International Symposium on Computer Architecture
  15. A Case for Multi-Programming Quantum Computers
    Poulami Das, Swamit Tannu, Prashant J. Nair, Moinuddin K. Qureshi · 2019 · IEEE/ACM International Symposium on Microarchitecture (MICRO)
  16. Noisy intermediate-scale quantum computers
    Bin Cheng, Xiu–Hao Deng, Xiu Quan Gu, Yu He, Guangchong Hu, Peihao Huang, Jun Li, Ben‐Chuan Lin, Dawei Lu, Yao Lu et al. · 2023 · Frontiers of Physics
  17. Quantum algorithms and the Fourier transform
    Richard Jozsa · 1998 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences
  18. Quantum computing: pro and con
    John P. Preskill · 1998 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences
  19. What is a quantum simulator?
    Johnson, Tomi H, Clark, Stephen R, Jaksch, Dieter · 2014 · EPJ Quantum Technology
  20. Quantum computation of scattering in scalar quantum field theories
    Stephen P. Jordan, Keith S. M. Lee, John P. Preskill · 2014 · Quantum Information and Computation
  21. Theory of hybrid dynamical systems and its applications to biological and medical systems
    Kazuyuki Aihara, Hideyuki Suzuki · 2010 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences
  22. Quantum Computational Complexity
    John Watrous · 2013 · Springer eBooks
  23. Quantum Computing 40 Years Later
    John P. Preskill · 2023 · CRC Press eBooks
  24. Equivalences and Separations Between Quantum and Classical Learnability
    Rocco A. Servedio, Steven J. Gortler · 2004 · SIAM Journal on Computing
  25. Time evolution of complexity: a critique of three methods
    Tibra Ali, Arpan Bhattacharyya, S. Shajidul Haque, Eugene H. Kim, Nathan Moynihan · 2019 · Journal of High Energy Physics
  26. Models of Quantum Complexity Growth
    Fernando G. S. L. Brandão, Wissam A Chemissany, Nicholas Hunter-Jones, Richard Kueng, John P. Preskill · 2021 · PRX Quantum
  27. Quantum communication and complexity
    Ronald de Wolf · 2002 · Theoretical Computer Science
  28. Quantum Walks for Computer Scientists
    Salvador Elías Venegas-Andraca · 2008 · Synthesis lectures on quantum computing
  29. Machines, Logic and Quantum Physics
    David Deutsch, ARTUR K. EKERT, Rossella Lupacchini · 2000 · Bulletin of Symbolic Logic
  30. Factoring with qutrits: Shor's algorithm on ternary and metaplectic quantum architectures
    Alex Bocharov, Martin Roetteler, Krysta M. Svore · 2017 · Physical Review A
  31. Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
    Barbara M. Terhal, David Peter Divincenzo · 2004 · Quantum Information and Computation
  32. Quantum Computing Review: A Decade of Research
    Sandeep K. Sood, Pooja · 2023 · IEEE Transactions on Engineering Management
  33. Quantum inference on Bayesian networks
    Low, Guang Hao, Yoder, Theodore J., Chuang, Isaac L. · 2014 · Physical Review A
  34. The BQP-hardness of approximating the Jones polynomial
    Dorit Aharonov, Itai Arad · 2011 · New Journal of Physics
  35. Quantum Kolmogorov Complexity
    André Berthiaume, Wim van Dam, Sophie Laplante · 2001 · Journal of Computer and System Sciences
  36. Quantum lower bound for the collision problem
    Scott Aaronson · 2002 · ACM Symposium on Theory of Computing (STOC)
  37. The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
    Victor Bapst, Laura Foini, Florent Krząkała, Guilhem Semerjian, Francesco Zamponi · 2012 · HAL
  38. Principles of Quantum Computation and Information - Volume I: Basic Concepts
    Giuliano Benenti, Giulio Casati, G. Strini · 2004 · WORLD SCIENTIFIC eBooks
  39. Efficient arbitrary simultaneously entangling gates on a trapped-ion quantum computer
    Nikodem Grzesiak, R. Blümel, Kenneth Wright, Kristin M. Beck, Neal C. Pisenti, Ming Li, Vandiver L. Chaplin, Jason Amini, Shantanu Debnath, Jwo-Sy Chen et al. · 2020 · Nature Communications
  40. QUANTUM COMPUTATION
    Dorit Aharonov · 1999 · WORLD SCIENTIFIC eBooks
  41. ALGORITHMS: A QUEST FOR ABSOLUTE DEFINITIONS
    Andreas R. Blass, Yuri G. Gurevich · 2004 · WORLD SCIENTIFIC eBooks
  42. Post hoc Verification of Quantum Computation
    Joseph F. Fitzsimons, Michal Hajdušek, Tomoyuki Morimae · 2018 · Physical Review Letters
  43. Confirmation via Analogue Simulation: What Dumb Holes Could Tell Us about Gravity
    Radin Dardashti, Karim P. Y. Thébault, Eric B. Winsberg · 2015 · The British Journal for the Philosophy of Science
  44. Molecular scale heat engines and scalable quantum computation
    Leonard J. Schulman, Umesh V. Vazirani · 1999 · ACM Symposium on Theory of Computing (STOC)
  45. Qubit devices and the issue of quantum decoherence
    Howard E. Brandt · 1999 · Progress in Quantum Electronics
  46. Learnability of Quantum Neural Networks
    Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, Dacheng Tao · 2021 · PRX Quantum
  47. Unbounded-error quantum computation with small space bounds
    Abuzer Yakaryılmaz, A. C. Cem Say · 2011 · Information and Computation
  48. An introduction to quantum information processing: applications and realizations
    Timothy P. Spiller, William J. Munro, S. D. Barrett, Pieter Kok · 2005 · Contemporary Physics
  49. A Quantum Goldreich-Levin Theorem with Cryptographic Applications
    Mark Adcock, Richard Cleve · 2002 · Lecture notes in computer science
  50. Histogram-based segmentation of quantum images
    Simona Caraiman, Vasile Manta · 2013 · Theoretical Computer Science
  51. Biology and medicine in the landscape of quantum advantages
    Cordier, Benjamin A., Sawaya, Nicolas P. D., Guerreschi, Gian Giacomo, McWeeney, Shannon K. · 2022 · Journal of The Royal Society Interface
  52. Quantum Computation of Scattering in Scalar Quantum Field Theories
    Stephen P. Jordan, Keith S. M. Lee, John P. Preskill · 2014 · CaltechAUTHORS (California Institute of Technology)
  53. Quantum Computing: 1-Way Quantum Automata
    Alberto Bertoni, Carlo Mereghetti, Beatrice Palano · 2003 · Lecture notes in computer science
  54. Quantum Circuits for Dynamic Runtime Assertions in Quantum Computation
    Ji Liu, Gregory T. Byrd, Huiyang Zhou · 2020 · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)
  55. A Survey of Quantum Property Testing
    Ashley Montanaro, Ronald de Wolf · 2016 · Theory of Computing
  56. Architecting Noisy Intermediate-Scale Trapped Ion Quantum Computers
    Prakash Murali, Dripto M. Debroy, Kenneth R. Brown, Margaret Martonosi · 2020 · Proceedings - International Symposium on Computer Architecture/Proceedings
  57. The Fourier spectrum of critical percolation
    Christophe Garban, Gábor Pete, Oded Schramm · 2010 · Acta Mathematica
  58. Computational model underlying the one-way quantum computer
    Robert Raussendorf, Hans J. Briegel · 2002
  59. Quantum Algorithm for Hilbert's Tenth Problem
    Tien D. Kieu · 2003 · International Journal of Theoretical Physics
  60. Quantum learning robust against noise
    Cross, Andrew W., Smith, Graeme, Smolin, John A. · 2015 · Physical Review A
  61. On universal and fault-tolerant quantum computing: a novel basis and a new constructive proof of universality for Shor's basis
    P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, Farrokh Vatan · 2003 · Annual Symposium on Foundations of Computer Science
  62. On the power of quantum computation
    Umesh V. Vazirani · 1998 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences
  63. One complexity theorist's view of quantum computing
    Lance Fortnow · 2003 · Theoretical Computer Science
  64. Quantum information processing in continuous time
    Andrew M. Childs, Edward Farhi · 2004 · DSpace@MIT (Massachusetts Institute of Technology)
  65. Implementation of quantum imaginary-time evolution method on NISQ devices by introducing nonlocal approximation
    Hirofumi Nishi, Taichi Kosugi, Yu‐ichiro Matsushita · 2021 · npj Quantum Information
  66. Quantum computers that can be simulated classically in polynomial time
    Leslie Gabriel Valiant · 2001 · ACM Symposium on Theory of Computing (STOC)
  67. Spins as qubits: Quantum information processing by nuclear magnetic resonance
    Dieter Suter, T. S. Mahesh · 2008 · The Journal of Chemical Physics
  68. An Introduction to Quantum Error Correction
    Daniel Gottesman · 2000 · arXiv (Cornell University)
  69. Expressive power of parametrized quantum circuits
    Yuxuan Du, Hsieh, M-H, Tongliang Liu, Dacheng Tao · 2018 · UTS ePRESS (University of Technology Sydney)
  70. Quantum Kolmogorov complexity based on classical descriptions
    Paul M. B. Vitanyi · 2001 · IEEE Transactions on Information Theory
  71. An Introduction to Quantum Complexity Theory
    Richard Cleve · 2001 · WORLD SCIENTIFIC eBooks
  72. Reflections for quantum query algorithms
    Ben W. Reichardt · 2011 · ACM-SIAM Symposium on Discrete Algorithms (SODA)
  73. A new protocol and lower bounds for quantum coin flipping
    Andris Ambainis · 2001 · ACM Symposium on Theory of Computing (STOC)
  74. Quantum abstract interpretation
    Nengkun Yu, Jens Palsberg · 2021 · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
  75. Quantum Algorithm Design: Techniques and Applications
    Changpeng Shao, Li Yang, Hongbo Li · 2019 · Journal of Systems Science and Complexity
  76. Phase-space-simulation method for quantum computation with magic states on qubits
    Robert Raussendorf, Juan Bermejo-Vega, Emily Tyhurst, Cihan Okay, Michael Zurel · 2020 · Physical Review A
  77. Automata theory based on quantum logic: some characterizations
    Daowen Qiu · 2004 · Information and Computation
  78. Counterfactual computation
    Graeme Mitchison, Richard Jozsa · 2001 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences
  79. Applications of coherent classical communication and the Schur transform to quantum information theory
    Aram W. Harrow · 2005 · arXiv (Cornell University)
  80. The Nature of Physical Computation
    Shagrir, Oron · 2022
  81. Quantum walk speedup of backtracking algorithms
    Ashley Montanaro · 2018 · Theory of Computing
  82. Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
    Stephen Fenner, Frederic Green, Steven Homer, Randall J. Pruim · 1999 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences
  83. Computational complexity in electronic structure
    Whitfield, James Daniel, Love, Peter John, Aspuru-Guzik, Alán · 2013 · Phys. Chem. Chem. Phys.
  84. Improved Bounds on Quantum Learning Algorithms
    Alp Atıcı, Rocco A. Servedio · 2005 · Quantum Information Processing
  85. Quantum Oracle Interrogation: Getting All Information for Almost Half the Price
    Wim Van Dam · 1998
  86. Bit-commitment-based quantum coin flipping
    Ashwin Nayak, Peter W. Shor · 2003 · Physical Review A
  87. Is quantum computing green? An estimate for an energy-efficiency quantum advantage
    Daniel Jaschke, Simone Montangero · 2022 · Quantum Science and Technology
  88. Quantum Error Correction in Spatially Correlated Quantum Noise
    Rochus Klesse, Sandra Frank · 2005 · Physical Review Letters
  89. Approximation and robustness of fuzzy finite automata
    Yongming Li · 2007 · International Journal of Approximate Reasoning
  90. A new protocol and lower bounds for quantum coin flipping
    Andris Ambainis · 2003 · Journal of Computer and System Sciences
  91. Quantum Automata with Open Time Evolution
    Mika Hirvensalo · 2010 · International Journal of Natural Computing Research
  92. Quantum Cryptography Based on the Deutsch-Jozsa Algorithm
    Koji Nagata, Tadao Nakamura, Ahmed Farouk · 2017 · International Journal of Theoretical Physics
  93. Interaction in quantum communication and the complexity of set disjointness
    Hartmut Klauck, Ashwin Nayak, Amnon Ta‐Shma, David Zuckerman · 2001 · ACM Symposium on Theory of Computing (STOC)
  94. "Quantum Supremacy" and the Complexity of Random Circuit Sampling
    Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani · 2018 · arXiv (Cornell University)
  95. Computational complexity of uniform quantum circuit families and quantum Turing machines Communicated by O. Watanabe
    Harumichi Nishimura, Masanao Ozawa · 2002 · Theoretical Computer Science
  96. A Survey of Continuous-Time Computation Theory
    Pekka Orponen · 1997 · Springer eBooks
  97. On randomization in sequential and distributed algorithms
    Rajiv Gupta, Scott A. Smolka, Shaji Bhaskar · 1994 · ACM Computing Surveys
  98. Quantum Computing for Computer Architects
    Tzvetan S. Metodi, Frederic T. Chong · 2006 · Synthesis lectures on computer architecture
  99. Pivoting makes the ZX-calculus complete for real stabilizers
    Ross Duncan, Simon Perdrix · 2014 · Electronic Proceedings in Theoretical Computer Science
  100. Teaching Quantum Computing to High-School-Aged Youth: A Hands-On Approach
    Prashanti Priya Angara, Ulrike Stege, Andrew MacLean, Hausi A. Müller, Tom Markham · 2021 · IEEE Transactions on Quantum Engineering