All reports by Author Niels Kornerup:

__
TR24-011
| 24th January 2024
__

Paul Beame, Niels Kornerup#### Quantum Time-Space Tradeoffs for Matrix Problems

Revisions: 1

__
TR23-005
| 13th January 2023
__

Paul Beame, Niels Kornerup#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

Revisions: 2

Paul Beame, Niels Kornerup

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 work. Our main results show that for a range of linear algebra problems---including matrix-vector product, matrix inversion, matrix multiplication and powering---existing ... more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>