The parts I can digest: Query complexity is about how much of the input needs to be read? Possibly about how many times each bit of the input needs to be read

The parts I can digest: Query complexity is about how much of the input needs to be read? Possibly about how many times each bit of the input needs to be read? There are different models of computation being compared: the familiar deterministic algo on classical computer, random algo (with zero error or with bounded error) on classical computer, and bounded error algo on quantum computer. They went looking for functions whose query complexity on different models of computation would have Interesting And Unexpected relationships. The (1) item basically means they found a function for which the gap in query complexity (between running a bounded-error algorithm on a quantum computer and a deterministic algorithm on a classical computer) is larger than previously conjectured; "there exists at least one problem for which the advantage a bounded-error quantum algorithm has over a deterministic algorithm is even bigger than previously thought."