Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
Quantum random access memory
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
A random access memory (RAM) uses n bits to randomly address N=2^n distinct memory cells. A quantum random access memory (qRAM) uses n qubits to address any quantum superposition of N memory cells. We present an architecture that exponentially reduces the requirements for a memory call: O(log N) switches need be thrown instead of the N used in conventional (classical or quantum) RAM designs. This yields a more robust qRAM algorithm, as it in general requires entanglement among exponentially less gates, and leads to an exponential decrease in the power needed for addressing. A quantum optical implementation is presented.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 3verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
Heterogeneous quantum architectures with task-specific hardware and QEC encodings deliver up to 138x lower physical-qubit overhead than monolithic baselines for fault-tolerant algorithms, including RSA-2048 factoring at 190k-381k qubits.
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
citing papers explorer
-
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
-
Heterogeneous architectures enable a 138x reduction in physical qubit requirements for fault-tolerant quantum computing under detailed accounting
Heterogeneous quantum architectures with task-specific hardware and QEC encodings deliver up to 138x lower physical-qubit overhead than monolithic baselines for fault-tolerant algorithms, including RSA-2048 factoring at 190k-381k qubits.
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.