Span programs and quantum space complexity While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of spacebounded quantum computation. We relate the quantum space complexity of computing a function f with onesided error to the logarithm of its span program size, a classical quantity that is wellstudied in attempts to prove formula size lower  the :59,more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (twosided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program  :130,no nontrivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first nontrivial lower bound on the approximate span program size of an explicit function.

A First Step to the Categorical Logic of Quantum Programs The longterm goal of our research is to develop a powerful quantum logic which is useful in the formal verification of quantum programs and protocols. In this paper we introduce the basic idea of our categorical logic of quantum programs (CLQP): It combines the logic of quantum programming (LQP) and categorical quantum mechanics (CQM) such that the advantages of both LQP and CQM are preserved while their disadvantages are overcome. We present the syntax, semantics and proof system of CLQP. As a proofofconcept, we apply CLQP to verify the correctness of Deutschxe2x80x99s algorithm and the concealing property of quantum bit commitment.