Ben Reichardt

The formula-evaluation problem is defined recursively. We give a quantum algorithm to evaluate formulas over any finite boolean gate set. Provided that the general adversary bound complexities of the input subformulas to any gate differ by at most a constant factor, the algorithm has optimal query complexity. Importantly, after efficient preprocessing, the algorithm is nearly time optimal. The algorithm is derived using the framework relating span programs and quantum algorithms. It corresponds to the composition of the individual span programs for each gate in the formula. We define a new span program complexity measure, the full witness size, allowing quantum algorithms to be based on span programs with free inputs.

We know that classical one-time memory is a cryptographic primitive which is sufficient to construct both classical one-time programs and quantum one-time programs. We propose a construction of one-time memory (OTM) from isolated Majorana islands. The proposed 1-out-of-2 OTM stores two bits, wherein any one chosen bit can be perfectly obtained, whereas the other bit is destroyed with high probability. We prove that a malicious recipient performing an arbitrary sequence of strong and weak measurements can not obtain more information than an honest recipient performing only strong measurements. We show that errors on the two stored bits can be corrected by a pair of classical codes obtained from a quantum CSS code. We compare several popular CSS codes and obtain the best codes for different regimes of physical error rate, availability of chosen bit and availability of remaining bit. Finally, we show that the construction for 1/2 OTMs can be generalized into efficient constructions for 1/n OTMs and (n−1)/n OTMs.