Ulysse Chabaud, Michael Joseph, Saeed Mehraban, and Arsalan Motamedi, "Bosonic quantum computational complexity." To be presented at the 16th Innovations in Theoretical Computer Science (ITCS 2025)
Dale Jacobs and Saeed Mehraban, "The Space Just Above One Clean Qubit." (arXiv:2410.08051)
Saeed Mehraban and Mehrdad Tahmasby. "Quadratic lower bounds on the approximate stabilizer rank: a probabilistic approach." (arXiv:2305.10277). Presented as a regular talk at the Quantum Information Processing (QIP 2024) 2024 and presented at the Symposium on Theory of Computing (STOC 2024) 2024.
Ulysse Chabaud and Saeed Mehraban. "Holomorphic representation of quantum computations." Presented at the 25th Annual Conference on Quantum Information Processing (QIP 2022), Published in Quantum, 6, 831 (2022). (arXiv:2111.00117)
Aram Harrow, Saeed Mehraban, and Mehdi Soleymanifar. "Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems." Presented at the Symposium on Theory of Computing (STOC 2020) (arXiv:1910.09071)
Enric Boix, Lior Eldar and Saeed Mehraban. "Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits." (arXiv:1912.03824)
Aram Harrow, Linghang Kong, Zi-Wen Liu, Saeed Mehraban, Peter Shor. "A separation of the out-of-time-ordered correlators and Entanglement." Published PRX Quantum, 2(2), 020339 (2021) (arXiv:1906.02219). Also Presented as a long talk at the 19th Asian Quantum Information Science Conference (AQIS 2019)
Aram Harrow, Saeed Mehraban. "Approximate unitary t-designs by random quantum circuits with nearest-neighbor and long-range gates." Presented as (one out of five) plenary talks at the 22nd Annual Conference on Quantum Information Processing (QIP 2019). Accepted in Communications in Mathematical Physics CIMP 2023. (arXiv:1809.06957)
Lior Eldar and Saeed Mehraban. "Approximating the Permanent of a Random Matrix with Vanishing Mean." Accepted at the 2018 Symposium on Foundations of Computer Science (FOCS 2018) (arXiv:1711.09457)
Scott Aaronson, Adam Bouland and Greg Kuperberg and Saeed Mehraban. "The Computational Complexity of Ball Permutations." Accepted at the 2017 Symposium on Theory of Computing (STOC 2017). I played the leading role on this project; this result was Based on my Master's thesis. (arXiv:1512.09243)
Saeed Mehraban, Amirhossein Shirazi, Maryam Zamani and Gholamreza Jafari. "Coupling between time series: a network view*." Published in 2013 EPL 103 50011. (arXiv:1301.1010)
Saeed Mehraban and Reza Ejtehadi. "A self-organized graph evolution model with preferential network random walk*." (arXiv:1205.7069v1)
Ph.D. Thesis
The complexity of sampling from a weak quantum computer Ph.D. Thesis, Submitted to MIT libraries, September 2019. Thesis supervisors: Scott Aaronson, UT Austin, Aram Harrow, MIT.
Master's Thesis
Computational Complexity of Some Quantum Theories in 1+1 Dimensions Master's Thesis, Submitted to MIT libraries, September 2015. Thesis supervisor: Scott Aaronson, UT Austin.
Talks:
Bosonic Quantum Computational Complexity, ITCS 2025, Columbia University [ Slides ]
(Invited) Bosonic Quantum Computational Complexity, delivered online by Arsalan Motamedi at UT Austin Fall 2024.
(Invited) Quadratic lower bounds on the approximate stabilizer rank: A Probabilistic Approach, University of Maryland, August 2024, and at STOC 2024, Vancouver, Canada. [ Slides ]
(Invited) Online talk at the Workshop on Quantum Information and Quantum Gravity, IPM, Tehran, Iran, August 2023 Title: "Approximate unitary t-designs by short-depth quantum circuits and applications", based on joint work with Aram Harrow.
(Invited) Online talk at IPM, Tehran, Iran, March 2023 Title: "Quantum-Inspired Permanent Identities", based on joint work with Ulysse Chabaud and Abhinav Deshpande.
(Invited) Online talk at the Microsoft Research Station Q, December 2021 Title: "Holomorphic Quantum Computing", based on joint work with Ulysse Chabaud.
(Invited) Online talk at the Mila Institute, Montreal, Canada, November 2021 Title: "Holomorphic Quantum Computing", based on joint work with Ulysse Chabaud.
(Invited) Talk at the CS Colloquium, Harvard University, Cambridge MA, USA, April 2021 Title: "Pseudo-randomness, complex zeros of polynomials, and hardness of sampling from small quantum devices"
(Invited) Talk at CS Colloquium, UT Austin Computer Science, Austin, TX, USA, March 2021 Title: "Pseudo-randomness, complex zeros of polynomials, and hardness of sampling from small quantum devices"
(Invited) Talk at UC Davis Computer Science, Medford, MA, USA, March 2021 Title: "Pseudo-randomness, complex zeros of polynomials, and hardness of sampling from small quantum devices"
(Invited) Talk at Tufts Computer Science, Medford, MA, USA, February 2021 Title: "Pseudo-randomness, average-case complexity, and hardness of sampling from small quantum devices"
(Invited) Talk at the Quantum Innovators in Computer Science and Mathematics, Institute for Quantum Computing at the University of Waterloo, October 2019 Title: "The old-new extrapolation technique and its quantum interfaces"
(Invited) Talk at the Institute at the Quantum Information, California Institute of Technology, April 2019 Title: "The complexity of sampling from a weak quantum computer", based on a joint works with Lior Eldar and Aram Harrow
(Invited) Talk at the Harvard Quantum Initiative Special Seminar, January 2019 Title: "The complexity of sampling from a weak quantum computer", based on a joint works with Lior Eldar and Aram Harrow
(Invited) "Approximate unitary t-designs by short random quantum circuits using nearest neighbor and long-range gates", American Mathematical Society (AMS) Sectional meeting, based on a joint work with Aram Harrow, Northeastern University, Boston, Massachusetts, USA, April 2018
(Invited) "Approximate unitary t-designs by short random quantum circuits using nearest neighbor and long-range gates" kickoff meeting for the IBM-MIT collaboration "Machine Learning in Hilbert Space", IBM Research, Yorktown Heights, USA, March 2018
(Invited) "Computational Complexity of Ball permutations", June 2017, complexity Sciences center, UC Davis, California USA
(Invited) "Representation theory of the symmetric group and BQP universality of permutation gates", UC Davis, California USA
(Invited) "Computational Complexity of Ball permutations", UT Austin, January 2017
