Quantum query complexity SDP source code
This page stores the Matlab source code to compute the quantum query
complexity SDP of Barnum, Saks and Szegedy, as used in the paper "On exact quantum query
complexity" by Ashley Montanaro, Richard Jozsa and Graeme Mitchison.
The code requires the CVX package
Usage: each function is parametrised by a pair (n,t), takes as input the truth table of a
boolean function on n variables, as a column vector, and returns the optimal success
probability of any quantum algorithm computing f using t queries.
- 2 variables: 1 query
- 3 variables: 1 query, 2 queries
- 4 variables: 1 query, 2 queries, 3
- 5 variables: 1 query, 2 queries, 3
queries, 4 queries
- 6 variables: 1 query, 2 queries, 3
queries, 4 queries, 5 queries
- eimat.m: helper function