## Research Areas at Uni Paderborn

At a high level, the Quantum Computing Lab at Uni Paderborn focuses primarily on the following two areas of research in theoretical computer science.

### Computational Complexity Theory

Computational complexity theory
is an area of computer science which studies the resources required, such as computing time or memory, to complete a given task. A specific focus of our group is on the subarea of *Quantum Hamiltonian Complexity*, which can be viewed as the study of physically motivated quantum generalizations of the Boolean Satisfiability Problem. Such ``quantum satisfiability problems'' are appealing in that they encode properties of physical quantum systems when cooled to low temperatures. The setting of *low* temperature, in particular, is interesting, as it is the regime in which certain exotic phenomena, such as superconductivity and superfluidity, manifest themselves. Here is a video demonstration, for example, of helium-4 undergoing a phase transition into the superfluid phase as it is cooled to near absolute zero.

### Algorithms

Algorithms are the heart and soul of much of computer science; they are what make Google's search engine, GPS directions, and just about every piece of software on your computer possible. Our lab pursues two main lines of algorithmic research. The first is the study of *classical* algorithms, such as exact or approximation algorithms, for computational problems arising in the setting of quantum mechanics. A standard such problem is that of estimating ground state energies of many-body quantum systems, also known as the Local Hamiltonian Problem. The second is the study of *quantum* algorithms, wherein the goal is to exploit the counterintuitive properties of quantum mechanics (such as superposition and entanglement) on a quantum computer in order to design algorithms which outperform classical computers.

For more information on any of these topics, please feel free to drop by Dr. Gharibian's office (see People).

## Publications

### Preprints

- S. Gharibian, M. Santha, J. Sikora, A. Sundaram and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). To appear in
*Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)*, and to also be presented as plenary talk (top 7% of submissions) at the*18th Asian Quantum Information Science Conference (AQIS 2018)*. Available at arXiv.org e-Print quant-ph/1805.11139, 2018. - M. Aldi, N. de Beaudrap, S. Gharibian and S. Saeedi. On efficiently solvable cases of Quantum 3-SAT. To appear in
*Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)*, and to also be presented as plenary talk (top 7% of submissions) at the*18th Asian Quantum Information Science Conference (AQIS 2018)*. Available at arXiv.org e-Print quant-ph/1712.09617, 2017. - A. Broadbent, S. Gharibian and H.-S. Zhou. Quantum one-time memories from stateless hardware. Available at arXiv.org e-Print quant-ph/1511.01363, 2015.

### Refereed Publications

- S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems.
*Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)*, volume 73 of*Leibniz International Proceedings in Informatics (LIPIcs)*, pages 2:1-2:17, 2018. Also presented as poster by Justin Yirka at QIP 2017. Video from Sev's talk at Leibniz Universität Hannover is available here. - N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT. In
*Proceedings of the 31st Conference on Computational Complexity (CCC)*, volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:21, 2016. Also presented at the*19th Conference on Quantum Information Processing (QIP)*, 2016. Open access preprint here. - S. Gharibian, Y. Huang, and Z. Landau, S. W. Shin. Quantum Hamiltonian Complexity.
*Foundations and Trends in Theoretical Computer Science*, 10(3):159-282, 2015. Open access preprint here. -
S. Gharibian, J. Sikora. Ground state connectivity of local Hamiltonians. In
*Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP)*, volume 9134 of Lecture Notes in Computer Science, pages 617 – 628, 2015. Full version in*ACM Transactions on Computation Theory*, volume 10, issue 2, 2018. Open access preprint here. - S. Gharibian, Z. Landau, S. W. Shin, and G. Wang. Tensor network non-zero testing.
*Quantum Information & Computation*15 (9 & 10):885-899, 2015. Presented by S. W. Shin as long talk at AQIS 2014. Open access preprint here. - S. Gharibian and J. Kempe. Hardness of approximation for quantum problems.
*Quantum Information & Computation*14 (5 & 6), 2014. Invited talk at ELC Workshop on Inapproximability, University of Electro-Communications, Japan. Also presented at QIP 2012, ICALP 2012. Open access preprint here. - D. Berry, R. Cleve and S. Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms.
*Quantum Information & Computation*14 (1 & 2): 0001-0030, 2014. Presented by R. Cleve at QIP 2012 and D. Berry at AQIS 2012. Open access preprint here. - S. Gharibian, J. Sikora, and S. Upadhyay. QMA variants with polynomially many provers
*. Quantum Information & Computation*13(1 & 2):0135-0157, 2013*. Open access preprint here.* - S. Gharibian. Quantifying non-classicality with local unitary operations,
*Physical Review A*86:042106, 2012. Invited talk at Mini-Workshop on the General Quantumness of Correlations, University of Waterloo, 2012. Open access preprint here. - S. Gharibian and J. Kempe. Approximation algorithms for QMA-complete problems,
*SIAM Journal on Computing*41(4): 1028-1050, 2012. Presented at CCC 2011. Winner of Best Poster Award at QIP 2011. Open access preprint here. - M. Piani, S. Gharibian, G. Adesso, J. Calsamiglia, P. Horodecki and A. Winter. All non-classical correlations can be activated into distillable entanglement,
*Physical Review Letters*106: 220403, 2011. Open access preprint here. - S. Gharibian, M. Piani, G. Adesso, J. Calsamiglia, P. Horodecki. Characterizing quantumness via entanglement creation,
*International Journal of Quantum Information*9(7 & 8):1701-1713, 2011. Open access preprint here. - S. Gharibian. Strong NP-hardness of the quantum separability problem,
*Quantum Information & Computation*10(3 & 4): 343-360, 2010. Winner of 2nd Place for Best Speaker Award, CQISC 2008. Also presented at SQuInT 2009. Open access preprint here. - S. Gharibian, H. Kampermann, and D. Bruß. On global effects caused by locally noneffective unitary operations,
*Quantum Information & Computation*9(11 & 12): 1013-1029, 2009. Invited talk by D. Bruß at QI 2009. Open access preprint here. - A. Datta and S. Gharibian. Signatures of non-classicality in mixed-state quantum computation,
*Physical Review A*79:042325, 2009. Open access preprint here.