Jeremiah Blocki

We introduce the parallel reversible pebbling game on directed graphs for constructing parallel quantum circuits that are efficient with respect to amortized space-time complexity (equivalently named cumulative complexity (CC)), a stronger metric than the conventional space-time complexity used for parallel algorithms. Our main result is a mapping from irreversible algorithms for computing a function, to quantum algorithms for computing the function in superposition, with just a sub-polynomial overhead in cumulative complexity. Thus, to construct a CC-efficient quantum oracle for a function, it suffices to solve the simpler problem of designing a CC-efficient classical algorithm for the function. This transformation also allows us to leverage the vast body of work on classical pebbling games for developing parallel quantum circuits with low amortized space-time complexity, given the data-dependency graph of the problem.

The random oracle model is a common setting for proving security of cryptographic primitives by replacing the underlying hash function with a uniformly random function. For some primitives, including memory-hard functions, proofs of sequential work, and proofs of space, security must be proved against highly parallel attackers, which motivates the parallel random oracle model. Existing quantum analogues of this model were introduced to study these primitives against quantum attackers, but they impose extra restrictions on the adversary’s parallel query sizes: one model fixes the same query size in every round, while another fixes the entire schedule of query sizes before the oracle is sampled. These restrictions have an unintended consequence, as there are problems for which a classical adaptive PROM algorithm uses asymptotically fewer queries than any quantum algorithm in the restricted PQROM models. We therefore introduce the adaptive PQROM, where the adversary may choose the next parallel query size after the previous oracle interaction, as the canonical quantum analogue of the classical PROM. We then extend compressed-oracle techniques to this setting and prove query bounds for natural problems including inversion, collision finding, k-sum, and proofs of sequential work.