Quantum Algorithm for Vector Interpolation
Abstract/Contents
- Abstract
- We study the functions that can be learned through the polynomial interpolation quantum algorithm designed by Childs et al. This algorithm was initially intended to find the coefficients of a multivariate polynomial function defined on finite fields F_q. We extend its scope to vector inner product functions of the form O_s(v) = s · v where the goal is to find the vector s in F_q. We examine the necessary conditions on the domain V of O_s and prove that the algorithm is optimal for such functions. Furthermore, we show that the success probability approaches 1 for large q and large domain order |V|. Finally, we provide a conservative formula for the number of queries required to achieve this success probability.
Description
| Type of resource | text |
|---|---|
| Date created | May 2021 |
Creators/Contributors
| Author | Decoppet, Sophie Marie |
|---|---|
| Primary advisor | Hayden, Patrick |
| Advisor | Boneh, Dan |
| Degree granting institution | Stanford University, Department of Physics |
Subjects
| Subject | quantum algorithm |
|---|---|
| Subject | vector interpolation |
| Subject | black box query |
| Genre | Thesis |
Bibliographic information
Access conditions
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Preferred citation
- Preferred Citation
- Decoppet, Sophie Marie. (2021). Quantum Algorithm for Vector Interpolation. Stanford Digital Repository. Available at: https://purl.stanford.edu/tq095bx1940
Collection
Undergraduate Theses, Department of Physics
View other items in this collection in SearchWorksContact information
- Contact
- sophiedecoppet@gmail.com
Also listed in
Loading usage metrics...