log in  |  register  |  feedback?  |  help  |  web accessibility
Quantum majority vote
Maris Ozols - University of Amsterdam
Thursday, January 19, 2023, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)

Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state ∣ψ_1⟩⊗⋯⊗∣ψ_n⟩ where each qubit ∣ψ_i⟩ is in one of two orthogonal states ∣ψ⟩ or ∣ψ^⊥⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/n). Under the promise that at least 2/3 of the input qubits are in the majority state, the fidelity increases to 1 − Θ(1/n) and approaches 1 as n increases.

We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}^n→{0,1} in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size O(n). The time complexity of the algorithm is O(n^4 log n) where n is the number of input qubits.

This is joint work with Harry Buhrman, Noah Linden, Laura Mančinska, and Ashley Montanaro.


This talk is organized by Andrea F. Svejda