# Accelerating Quantum Algorithms with Precomputation

**Authors:** William J. Huggins, Jarrod R. McClean  
**arXiv:** [2305.09638](https://arxiv.org/abs/2305.09638)  
**Date:** 2023-05-16  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2305.09638v1/

## Key points

- Authors explore the concept of quantum precomputation and its potential to accelerate real-world time-sensitive computing tasks
- Propose a cost model for quantum algorithms that allows for "free" computation before input is fully specified
- Analyze two families of unitaries within the cost model and compare their efficiency to the standard model
- Unitaries are found to be asymptotically more efficient in the proposed cost model, suggesting advantages of quantum precomputation
- First example: density matrix exponentiation offers exponential advantage compared to conventional methods under certain conditions
- Second example: variant of gate teleportation enables quadratic advantage when implementing unitaries directly
- Quantum precomputation can potentially accelerate time-sensitive tasks and improve computational efficiency by performing computations ahead of time
- Research provides valuable insights into quantum precomputation and its implications for accelerating computing tasks in real-world scenarios

## Summary

In their paper titled "Accelerating Quantum Algorithms with Precomputation," authors William J. Huggins and Jarrod R. McClean explore the concept of quantum precomputation and its potential to accelerate real-world time-sensitive computing tasks. They propose a cost model for quantum algorithms that allows for a polynomial amount of "free" computation before the input to an algorithm is fully specified, and they investigate methods for taking advantage of this precomputation. The authors analyze two families of unitaries within this cost model and compare their efficiency to the standard model. They find that these unitaries are asymptotically more efficient in the proposed cost model, suggesting that quantum precomputation could offer advantages over traditional approaches. The first example of quantum precomputation discussed in the paper is based on density matrix exponentiation. Under certain conditions, this approach could provide an exponential advantage compared to conventional methods. The second example involves using a variant of gate teleportation, which enables a quadratic advantage when implementing the unitaries directly. These examples highlight the potential benefits of quantum precomputation and suggest that it may open up new avenues for achieving quantum advantage in various applications. By performing some computations ahead of time, researchers can potentially accelerate time-sensitive tasks and improve overall computational efficiency. Overall, this research provides valuable insights into the concept of quantum precomputation and its implications for accelerating computing tasks in real-world scenarios. The findings contribute to ongoing efforts in exploring novel approaches to harnessing the power of quantum computing for practical applications.