Theory of Quantum Computation and Communication

If we had large-scale quantum computers and networks, what problems could they solve?
Theoretical work plays an important role in guiding the development of quantum technologies for computing and communication. It helps identify tasks – such as simulating quantum systems, enabling secure communication over untrusted networks, and solving hard problems in optimization, number theory and other areas of computational science – where quantum computers and networks can have large advantages over their classical counterparts. It addresses fundamental questions about the feasibility of performing large-scale quantum computation on realistic physical hardware, as well as the security of classical cryptography in a world where adversaries have large quantum computers.
Examples of QuICS research in this area include theoretical work on quantum algorithms, computational complexity, algorithms for quantum simulation, quantum machine learning, quantum and post-quantum cryptography, and quantum error correction and fault tolerance.
Related Publications
Quantum Algorithms and the Power of Forgetting
, , 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 251, 37:1–37:22, (2023)High-precision quantum algorithms for partial differential equations
, , Quantum 5, 574, 5, (2021)Efficient quantum algorithm for dissipative nonlinear differential equations
, , Proceedings of the National Academy of Sciences, 118, (2021)Symmetries, graph properties, and quantum speedups
, , Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020), (2020)Simulating large quantum circuits on a small quantum computer
, , Phys. Rev. Lett., 125, (2020)Tight bounds on the convergence of noisy random circuits to the uniform distribution
, , PRX Quantum, 3, (2022)PRXQuantum.3.040329.pdfComputations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
, , Symposium on the Theory of Computing (STOC) 2020 conference, (2020)Faster Digital Quantum Simulation by Symmetry Protection
, , Prx Quantum, 2, (2021)Theory of Trotter Error with Commutator Scaling
, , Physical Review X, 11, (2021)Faster quantum simulation by randomization
, , Quantum, 3, (2019)Toward the first quantum simulation with quantum speedup
, , Proceedings of the National Academy of Sciences, 115, 9456–9461, (2018)Provably efficient machine learning for quantum many-body problems
, , Science, 377, (2022)Sublinear quantum algorithms for training linear and kernel-based classifiers
, , Proceedings of the 36th International Conference on Machine Learning (ICML 2019) PMLR, 97, 3815–3824, (2019)Quantum Wasserstein Generative Adversarial Networks
, , Advances in Neural Information Processing Systems (NIPS), 32, (2019)Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
, , arXiv, (2023)Lattice-Based Quantum Advantage from Rotated Measurements
, , Quantum, 8, 1399, (2024)Post-Quantum Security of the Even-Mansour Cipher
, , Advances in Cryptology – EUROCRYPT 2022, 458–487, (2022)The impossibility of efficient Quantum weak coin flipping
, , STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 916–929, (2020)Pseudorandom States, Non-Cloning Theorems and Quantum Money
, , In: Shacham H., Boldyreva A. (eds) Advances in Cryptology – CRYPTO 2018. CRYPTO 2018. Lecture Notes in Computer Science., 10993, (2018)Complexity and order in approximate quantum error-correcting codes
, , Nature Physics, 20, 1798–1803, (2024)On stability of k-local quantum phases of matter
, , arXiv, (2024)Toward a 2D Local Implementation of Quantum LDPC Codes
, , PRX Quantum, 6, (2025)PRXQuantum.6.010306.pdfQuantum spherical codes
, , Nature Physics, 20, 1300-1305, (2024)Opportunities and Challenges in Fault-Tolerant Quantum Computation
, , arXiv, (2022)