I am a PhD student in the Theory Group at Columbia advised by Henry Yuen, and before that I was a graduate student at the Institute for Quantum Computing at the University of Waterloo, advised by John Watrous. I study theoretical computer science, with a focus on quantum computation.

My research is broadly about understanding fully-quantum tasks, including quantum cryptography, unitary complexity theory, and algorithms for learning from quantum data. Some specific problems that I think about are algorithms for shadow tomography, the complexity of unitary synthesis problems, and various topics in quantum cryptography like quantum money and pseudo-randomness. I am generally happy to talk about anything related to computer science, so if you have a question or idea please feel free to reach out to me!

Email: johnb at cs dot columbia dot edu

Papers

• Learning the closest product state. Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O’Donnell, and Ewin Tang. Preprint [pdf, arXiv]

• A General Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire. John Bostanci, Barak Nehoran, and Mark Zhandry. Preprint. [pdf, arXiv, eprint]

• Pseudorandomness in the (Inverseless) Haar Random Oracle Model. Prabhanjan Ananth, John Bostanci, Aditya Gulati, and Yao-Ting Lin. Preprint. [pdf, arXiv, eprint]

• Commuting Local Hamiltonians Beyond 2D. John Bostanci and Yeongwoo Hwang. Preprint. [pdf, arXiv, eccc]

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States. John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba. Preprint. [pdf, arXiv, eprint]

• Oracle Separation Between Quantum Commitments and Quantum One-wayness. John Bostanci, Boyang Chen, Barak Nehoran. Preprint. [pdf, arXiv, eprint]

• An efficient quantum parallel repetition theorem and applications. John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen. STOC 2024, QIP 2024 Short Plenary Talk. [pdf, arXiv, eprint, eccc, slides]

• Unitary Complexity and the Uhlmann Transformation Problem. John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen. Preprint. QIP 2024 Long Plenary Talk. [pdf, arXiv]

• Quantum Event Learning and Gentle Random Measurements. Adam Bene Watts and John Bostanci. ITCS 2024 [pdf, arXiv, slides, talk].

• Finding the disjointness of stabilizer codes is NP-complete. John Bostanci and Aleksander Kubica. Physical Review Research 3, 2021. [pdf, arXiv]

• Quantum game theory and the complexity of approximating quantum Nash equilibria. John Bostanci and John Watrous. Quantum 6, 2022. [pdf, arXiv]

Teaching

In Fall 2022 I was a TA for Introduction to Quantum Computing at Columbia, taught by Henry Yuen.

In Summer 2023 I was a TA for Topological Aspects of Error Correcting Codes at the Park City Mathematics Institute Graduate Summer School, taught by Jeongwan Haah. Click here to see the problem sets and solutions.

Work Experience

In the summer of 2024, I was an intern at NTT Research working with Mark Zhandry.

I used to work for a start-up derivatives exchange called Kalshi, where I helped design and build the exchange, as well as designed and built most of the connections with external parties including Bloomberg, brokers, and market makers.

I also used to work for Citadel on the Alpha Research and Development team. Some of my projects include X-Alpha (a graph based resource manager for creating terms), and Leonov (a neural architecture that performed better than human modelers on near term alpha).