We construct a total Boolean function f satisfying R ( f ) = ( Q ( f ) 5 2 ) , refuting the long-standing conjecture that R ( f ) = O ( Q ( f ) 2 ) for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to R ( f ) = ( Q ( f ) 3 ) . Our construction is motivated by the G??s-Pitassi-Watson function but does not use it.
展开▼
