9 citations · 17 across the 7 of their papers we have counts for
9 papers
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeo…
Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
Paul Beame, Niels Kornerup, Michael Whitmeyer
Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state…
Computational foundations of the human world
Marcus J. Hamilton, Abhishek Yadav, Harrison Hartle +10
Human societies continuously transform scattered information into collective judgments and coordinated action, whether through markets discovering prices, governments allocating re…
Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame, Niels Kornerup, Michael Whitmeyer
We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior wor…
Harvesting Brownian Motion: Zero Energy Computational Sampling
David Doty, Niels Kornerup, Austin Luchsinger +3
The key factor currently limiting the advancement of computational power of electronic computation is no longer the manufacturing density and speed of components, but rather their…
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
Paul Beame, Niels Kornerup
Cumulative memory -- the sum of space used per step over the duration of a computation -- is a fine-grained measure of time-space complexity that was introduced to analyze cryptogr…
Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
Niels Kornerup, Jonathan Sadun, David Soloveichik
Pebble games are popular models for analyzing time-space trade-offs. In particular, the reversible pebble game is often applied in quantum algorithms like Grover's search to effici…
Composable Rate-Independent Computation in Continuous Chemical Reaction Networks
Cameron Chalk, Niels Kornerup, Wyatt Reeves +1
Biological regulatory networks depend upon chemical interactions to process information. Engineering such molecular computing systems is a major challenge for synthetic biology and…
Review of a Quantum Algorithm for Betti Numbers
Sam Gunn, Niels Kornerup
We looked into the algorithm for calculating Betti numbers presented by Lloyd, Garnerone, and Zanardi (LGZ). We present a new algorithm in the same spirit as LGZ with the intent of…