COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > Efficient Quantum State Synthesis with One Query

## Efficient Quantum State Synthesis with One QueryAdd to your list(s) Download to your calendar using vCal - Gregory Rosenthal, CST, University of Cambridge
- Thursday 09 November 2023, 14:15-15:30
- MR2.
If you have a question about this talk, please contact Sergii Strelchuk. We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ⟩ there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ⟩. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following: • We simplify the proof that statePSPACE ⊆ stateQIP (a quantum state analogue of PSPACE ⊆ IP) and show that a constant number of rounds of interaction suffices. • We show that QACf0 lower bounds for constructing explicit states would imply breakthrough circuit lower bounds for computing explicit boolean functions. • We prove that every n-qubit state can be constructed to within 0.01 error by an O(2^n/n)-size circuit over an appropriate finite gate set. More generally we give a size-error tradeoff which, by a counting argument, is optimal for any finite gate set. To appear in SODA 2024 . Paper available at https://arxiv.org/abs/2306.01723. This talk is part of the CQIF Seminar series. ## This talk is included in these lists:- All CMS events
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- MR2
- bld31
Note that ex-directory lists are not shown. |
## Other listsMachine Learning Stats Best updates for everyone## Other talksDiscovery of potent broadly neutralizing antibodies against dengue virus using a targeted E dimer probe Quasi-universal sheaves and generic bricks The myth of archaic introgression into humans: 3 more telling vignettes! Welcome and Introduction The cartographic commissions of John, 2nd Duke of Montagu (1690–1749) Space-time fractional diffusion equations in chemotaxis and immunology |