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.

Recent examples of QuICS research in this area include theoretical work on quantum algorithms [A1-A4], computational complexity [B1-B2], algorithms for quantum simulation [C1-C4], quantum machine learning [D1-D3], quantum and post-quantum cryptography [E1-E5], and quantum error correction and fault tolerance [F1-F5].

References:

A.

1. “Quantum Algorithms and the Power of Forgetting,” http://dx.doi.org/10.4230/LIPIcs.ITCS.2023.37 
2. “High-precision quantum algorithms for partial differential equations,” https://quantum-journal.org/papers/q-2021-11-10-574/ 
3. “Efficient quantum algorithm for dissipative nonlinear differential equations,” https://www.pnas.org/doi/full/10.1073/pnas.2026805118 
4. “Symmetries, graph properties, and quantum speedups,” https://doi.org/10.1109/FOCS46700.2020.00066 
5. “Simulating large quantum circuits on a small quantum computer,” https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.125.150504 

B. 

1. “Tight bounds on the convergence of noisy random circuits to the uniform distribution,” https://link.aps.org/doi/10.1103/PRXQuantum.3.040329 
2. “Computations with greater quantum depth are strictly more powerful (relative to an oracle),” https://dl.acm.org/doi/abs/10.1145/3357713.3384269 

C.

1. “Faster digital quantum simulation by symmetry protection,” https://link.aps.org/doi/10.1103/PRXQuantum.2.010323 
2. “Theory of Trotter Error with Commutator Scaling,” https://link.aps.org/pdf/10.1103/PhysRevX.11.011020 
3. “Faster quantum simulation by randomization,” https://quantum-journal.org/papers/q-2019-09-02-182/ 
4. “Toward the first quantum simulation with quantum speedup,” https://www.pnas.org/doi/abs/10.1073/pnas.1801723115 

D.

1. “Provably efficient machine learning for quantum many-body problems,” https://www.science.org/doi/abs/10.1126/science.abk3333 
2. “Sublinear quantum algorithms for training linear and kernel-based classifiers,” http://proceedings.mlr.press/v97/li19b.html 
3. “Quantum Wasserstein generative adversarial networks,” https://proceedings.neurips.cc/paper/2019/hash/f35fd567065af297ae65b621e0a21ae9-Abstract.html 

E.

1. “Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model,” https://link.springer.com/chapter/10.1007/978-3-031-58751-1_15 
2. “Lattice-based quantum advantage from rotated measurements,” https://quantum-journal.org/papers/q-2024-07-04-1399/ 
3. “Post-quantum security of the Even-Mansour cipher,” https://link.springer.com/chapter/10.1007/978-3-031-07082-2_17 
4. “The impossibility of efficient quantum weak coin flipping,” https://dl.acm.org/doi/abs/10.1145/3357713.3384276 
5. “Pseudorandom quantum states,” https://link.springer.com/chapter/10.1007/978-3-319-96878-0_5 

F.

1. “Complexity and order in approximate quantum error-correcting codes,” https://doi.org/10.1038/s41567-024-02621-x 
2. “On stability of k-local quantum phases of matter,” https://arxiv.org/pdf/2405.19412 
3. “Toward a 2D Local Implementation of Quantum LDPC Codes,” https://arxiv.org/abs/2404.17676 
4. “Quantum spherical codes,” https://www.nature.com/articles/s41567-024-02496-y 
5. “Opportunities and challenges in fault-tolerant quantum computation,” https://arxiv.org/abs/2210.15844