Rice University expert receives Google Scholar Award

Baseball, cryptography, and Hamiltonians are rarely found in the same conversation, unless it is with Rice University quantum computer scientist Nai-Hui Chia. His interest in studying Hamiltonians, a method for representing the motion of a system or cluster of moving particles, resulted in a Google Scholar Award to fund new research in quantum computing.

“We hope to determine whether or not quantum computers (or any programmable quantum machines) can simulate a specific type of physical system described as a ‘Hamiltonian matrix’ — and do so with a simulation time that is strictly shorter than the evolution time, using parallelism or additional classical computation resources,” said Chia, assistant professor of computer science.

He used a baseball pitch analogy to illustrate a more rapid simulation of a Hamiltonian matrix. “Let’s predict the end location of a four-seam fastball. A great batter intuitively calculates that prediction and swings accordingly. On the other hand, it is hard to predict the end location of a knuckleball before the catcher snags it. Making that kind of prediction is our motivation. Can we identify physical systems in which we can make a prediction earlier and those in which we cannot? We call this fast-forwarding for a Hamiltonian simulation.”

Simulating quantum systems has been viewed as an important application of quantum computers because quantum computers can outperform their classical counterparts in rapidly solving complex problems. Chia said scientists have not yet determined if quantum computers can actually help parallelly fast-forward the Hamiltonian simulation.

“Although several nice studies have presented results demonstrating the potential or impossibility of fast-forwarding in simulating specific Hamiltonians, it remained unclear whether parallelism could aid in achieving fast-forwarding of Hamiltonian simulation,” said Chia.

“We also want to know whether parallel fast-forwarding is possible by interweaving classical computers with ‘near-term quantum computers.’ Here, we want to know if the circuit depth of the quantum computer can be strictly less than the evolution time.”

Chia plans to use the Google Scholar Award in a project to identify Hamiltonians that can be fast-forwarded and/or those impossible to fast-forward under plausible computation primitives. He plans to build on his recent ‘impossibility’ research, to be presented in July at the 2023 Computational Complexity Conference in Warwick, UK. Surprisingly, Chia’s initial impossibility research focused on cryptography — the use of codes to hide or secure communications and payment transaction details.

“At CCC2023, we will present a paper, “On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation,” showing that under certain well-believed cryptographic assumptions, there exist local Hamiltonians and sparse Hamiltonians that cannot be parallelly fast-forwarded,” said Chia.

A cryptography premise long considered to be very reliable is the sequential puzzle. This theory has been used in popular movies where solving one puzzle provides a clue to the next puzzle, eventually leading to the discovery of a hidden treasure or threat. If the sequence is broken, the information about the location cannot be recovered.

“Roughly speaking, in cryptography, we believe some puzzles can only be solved one by one,” said Chia. “But we showed that if one can parallelly fast-forward some Hamiltonians, one can do several such puzzles together! Our result is the first impossibility result about parallel fast-forwarding.

“However, it is unclear whether our impossibility result can be extended to hybrid quantum-classical computation, where we want to know if the quantum circuit depth can be strictly less than the evolution time. Also, we want to know if we can obtain similar impossibility results under weaker assumptions and for more general Hamiltonians.”

He acknowledged that several previous works proved that some Hamiltonians, such as diagonalizable Hamiltonians, can be fast-forwarded. In the research project funded by Google, Chia aims to discover more such Hamiltonians when using parallelism or allowing classical computation.

Hamiltonians fit well with Chia’s research interests: quantum cryptography, quantum complexity theory, and quantum algorithms. A quantum physics fan since childhood, he wants to understand quantum computing’s capabilities, limits, and how it could change computer science.

“Studying whether quantum computers can parallelly fast-forward Hamiltonian simulations is one of the directions I want to explore to further understand the capability of quantum computers,” he said.

“In addition, I am particularly interested in the ‘connections’ between all these fields in quantum computer science. The results we present at CCC2023 for this project provide a nice example that connects cryptography and Hamiltonian simulation, a connection that quite surprised me.”