SQuInT 2022 Program
Full Program | Thursday | Friday | Saturday | All Sessions | Posters | Talks
SESSION 4: Quantum algorithms (Islands Ballroom)Chair: (Nathan Wiebe (Toronto)) | |
| 3:15 pm - 3:45 pm | Joonho Lee, Google A path forward for achieving practical quantum advantage in chemistry | Abstract. In this talk, I will describe a new hybrid algorithm, quantum-classical hybrid quantum Monte Carlo (QC-QMC), that has demonstrated accurate quantum computations of chemical systems beyond what has been possible with other variational NISQ algorithms. I will explain what algorithms need to consider when showing practical quantum advantages and why QC-QMC has attractive features. I will also remark on challenges in QC-QMC that must be considered when designing one of the first demonstrations for quantum advantage in chemistry. This talk is meant to engage both chemistry and quantum information science audiences as the synergistic interactions between the two are critical. |
| 3:45 pm - 4:15 pm | Anirban Chowdhury, Institute for Quantum Computing Classical and quantum algorithms for trace estimation | Abstract. Estimating the trace of matrix functions is a problem commonly encountered in physics. In this talk I will present improved exponential-time classical and quantum algorithms for the problem of trace estimation, with the partition function as a specific example. I will summarize techniques to evaluate traces of block-encoded operators on quantum devices. I will show that a compression technique based on unitary 2-designs leads to a qubit-efficient quantum algorithm for estimating partition functions. I will then discuss how the same compression idea also leads to a classical algorithm with improved running-time. Lastly, I will mention some complexity theoretic results regarding the hardness of this problem. The talk will be based on some results from arXiv:2110.15466. |
| 4:15 pm - 4:45 pm | Burak Sahinoglu, PsiQuantum Quantum algorithms from fluctuation theorems: Thermal-state preparation | Abstract. Fluctuation theorems provide a correspondence between properties of quantum systems in thermal equilibrium and a work distribution arising in a non-equilibrium process that connects two quantum systems with Hamiltonians \(H_0\) and \(H_1=H_0+V\). Building upon these theorems, we present a quantum algorithm to prepare a purification of the thermal state of \(H_1\) at inverse temperature \(\beta \ge 0\) starting from a purification of the thermal state of \(H_0\). The complexity of the quantum algorithm, given by the number of uses of certain unitaries, is \(\tilde {\cal O}(e^{\beta (\Delta \! A- w_l)/2})\), where \(\Delta \! A\) is the free-energy difference between \(H_1\) and \(H_0,\) and \(w_l\) is a work cutoff that depends on the properties of the work distribution and the approximation error \(\epsilon>0\). If the non-equilibrium process is trivial, this complexity is exponential in \(\beta \|V\|\), where \(\|V\|\) is the spectral norm of \(V\). This represents a significant improvement of prior quantum algorithms that have complexity exponential in \(\beta \|H_1\|\) in the regime where \(\|V\|\ll \|H_1\|\). The dependence of the complexity in \(\epsilon\) varies according to the structure of the quantum systems. It can be exponential in \(1/\epsilon\) in general, but we show it to be sublinear in \(1/\epsilon\) if \(H_0\) and \(H_1\) commute, or polynomial in \(1/\epsilon\) if \(H_0\) and \(H_1\) are local spin systems. The possibility of applying a unitary that drives the system out of equilibrium allows one to increase the value of \(w_l\) and improve the complexity even further. To this end, we analyze the complexity for preparing the thermal state of the transverse field Ising model using different non-equilibrium unitary processes and see significant complexity improvements. |
- Home
- Register for Workshop
- Program
- Submit Your Abstract
- Instructions for Presenters
- Location
- Subscribe to the SQuInT Mailing List
- Code of Conduct
- Past SQuInT Meetings
SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu
SQuInT Co-Organizer
Hartmut Haeffner, Associate Professor, UC Berkeley
hhaeffner@berkeley.edu
SQuInT Administrator
Dwight Zier
d29zier@unm.edu
505 277-1850
SQuInT Program Committee
Alberto Alonso, Postdoc, UC Berkeley
Philip Blocher, Postdoc, UNM
Neha Yadav, Postdoc, UC Berkeley
Cunlu Zhou, Postdoc, UNM
SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director
ideutsch@unm.edu
