University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Exact quantum algorithms

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Exact quantum algorithms

Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani .

Mathematical Challenges in Quantum Information

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1) – in contrast to the usual model in which a quantum algorithm is allowed to output an incorrect answer with a small probabilities. Coming up with exact quantum algorithms is a difficult task because we have to ensure that no amplitude ends up in a state corresponding to an incorrect answer – on any input.

We present the first example of a Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675…}) queries.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Name to be confirmed David Attenborough Building, New Museums Site, Room 3.41 Marine/Wolfson Building lecture hall

Other talks

How bubble acoustics can help in three apocalypses A Novel Diffusion Model based Approach for Sleep Music Generation Nationalising Oil and Knowledge in Iran: Labour, Decolonisation and Colonial Modernity, 1933–51 From Surrogate Solvers to PINNs and Beyond Classical Methods Wolfson Tool Factory Title to be confirmed
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity