Introduction

A quantum algorithm is often described by its number of qubits and gates. Those resources matter, but for data-intensive algorithms they do not tell the whole story. A quantum computer may have enough qubits to run a circuit, and the circuit may use a famous quantum subroutine, yet the algorithm can still fail to offer an advantage because the numerical data were encoded too cheaply.

This book studies that problem.

The central question is:

If we reduce exact digital quantum memory, how many more quantum queries must we pay in execution time to recover, resolve, or use the same numerical information?

The answer is not merely an engineering detail. It is an information-theoretic constraint. High-precision numerical data cannot be made available to a quantum algorithm for free. If we store fewer exact bits in qubit registers, then the missing precision must be carried somewhere else. One tempting place is a smooth quantum phase: instead of storing a number as a binary string, we encode it as an angle in a rotation. But a phase that differs by a tiny amount from another phase is not automatically usable information. To exploit it, the algorithm must distinguish the corresponding quantum states, and that requires queries, repetitions, coherent evolution time, or some equivalent physical resource. This is where memory and execution time meet.

Quantum information theory already teaches us that quantum states, measurements, and distinguishability are constrained by the rules of Hilbert space, density operators, and measurement statistics; these are standard foundations of the field, as developed for example in Nielsen and Chuang’s textbook on quantum computation and quantum information (Nielsen and Chuang, 2010). Quantum detection and estimation theory further studies how well states and parameters can be inferred from measurements (Helstrom, 1976; Holevo, 1982). Quantum metrology sharpens this point for continuous parameters: with bounded generators and suitable coherence, phase resolution can scale like the inverse of the total query or interrogation resource, often called Heisenberg-limited scaling in the ideal setting (Giovannetti, Lloyd, and Maccone, 2006; Giovannetti, Lloyd, and Maccone, 2011). This book brings these ideas into one focused resource question: what happens when high-precision numerical data are split between exact digital qubits and continuous phase rotations?

The first picture: exact memory versus phase memory

Start with an ordinary number, such as

\[ x = 0.734918\ldots \]

A classical computer stores an approximation to this number using bits. For example, a 64-bit floating-point representation stores a finite amount of information about \(x\). It does not store the real number with infinite precision; it stores a carefully specified approximation.

A quantum computer can also store digital information. An \(r\)-qubit register has \(2^r\) computational basis states,

\[ |0\rangle, |1\rangle, \ldots, |2^r-1\rangle, \]

so it can hold an \(r\)-bit classical label reversibly when used in the computational basis. In this book, digital qubit memory means qubits used to store discrete, exactly addressable binary information, such as a fixed-point approximation, an index, or a controlled branch label.

But quantum systems also have phases. A simple one-qubit phase rotation has the form

\[ R_z(\theta) = \begin{pmatrix} e^{-i\theta/2} & 0 \\ 0 & e^{i\theta/2} \end{pmatrix}. \]

The angle \(\theta\) is a continuous parameter in the mathematical description of the unitary. It is therefore tempting to encode many bits of a number into a single angle. For instance, instead of storing a 40-bit fractional number in a 40-qubit register, one might try to set

\[ \theta = 2\pi x \]

and allow the algorithm to access the unitary \(R_z(\theta)\). This is the beginning of continuous phase encoding.

The danger is subtle. The symbol \(\theta\) may contain infinitely many mathematical digits, but the algorithm does not automatically receive those digits. It receives access to a physical operation. If two candidate angles differ by

\[ \Delta \theta = 2^{-40}, \]

then distinguishing them requires enough interaction with the corresponding unitary to resolve that separation. In the ideal noiseless model, repeated or coherent uses of the unitary can amplify the distinguishability of nearby phases, but the required query count still grows as the desired resolution becomes finer under bounded-generator assumptions (Giovannetti, Lloyd, and Maccone, 2006; Giovannetti, Lloyd, and Maccone, 2011).

This is the first lesson of the book:

A smooth phase is not free digital memory. It becomes usable numerical information only through queries, measurements, and estimation.

What is a query?

A query is one controlled access to a specified data-dependent operation. In many quantum algorithms, the detailed circuit between queries is less important than the number of times the algorithm must call the oracle, block-encoding, controlled rotation, or state-preparation routine that contains the input data.

For example, suppose a data value \(x\) is encoded through a rotation

\[ U_x = e^{-i x G}, \]

where \(G\) is a Hermitian generator. One query means one use of \(U_x\), \(U_x^\dagger\), or a controlled version of such an operation, depending on the model. If an algorithm calls this operation \(q\) times, then \(q\) is its quantum query complexity with respect to that data source.

Query complexity is not always identical to wall-clock runtime. A single query might be cheap or expensive depending on compilation, memory access, fault-tolerant synthesis, hardware connectivity, and error correction. Still, query complexity is a central abstraction because many quantum speedups are expressed in terms of fewer oracle or data-access calls. Amplitude estimation, for example, obtains a quadratic improvement in dependence on additive error compared with simple classical Monte Carlo sampling in the ideal query model (Brassard et al., 2002; Montanaro, 2015). Block-encoding frameworks similarly organize many quantum linear-algebra algorithms around repeated access to structured unitary representations of data or operators (Gilyén et al., 2019).

This book treats query complexity as an execution-time resource, while repeatedly asking when that abstraction is honest. A query lower bound is meaningful only after we specify what the query gives us, what is counted as free, and how accurately the encoded data must be used.

Hybrid data encoding

The main object of study is a hybrid quantum data encoding. The word hybrid means that numerical information is divided between two kinds of resources:

1. Exact digital qubits, counted by \(r\), which store discrete bits or labels.
2. Continuous phase-rotation channels, counted by \(m\), which encode remaining numerical information in smooth parameters.

A simple example is a number whose first \(r\) bits are stored digitally, while the remaining bits are placed into one or more phase rotations. Suppose a target number \(x\in[0,1)\) has an \(n\)-bit approximation

\[ x \approx 0.b_1 b_2 \cdots b_n. \]

A purely digital encoding would store all \(n\) bits. A hybrid encoding might store

\[ b_1,\ldots,b_r \]

in an \(r\)-qubit register, while the remaining \(n-r\) bits are encoded into phase parameters. If there is only one phase channel, then that single channel must carry all displaced precision. If there are \(m\) channels, the displaced precision may be distributed across them.

This distribution is the core design choice.

For a concrete scale, imagine that a computation needs 64 bits of numerical precision. If only \(r=40\) bits are stored digitally, then 24 bits have been displaced into phase degrees of freedom. With one phase channel, resolving those 24 bits means resolving phase differences on the order of \(2^{-24}\). Under the ideal bounded-generator model, that suggests a query scale on the order of \(2^{24}\). But if the same displaced information is spread evenly across \(m=4\) independent channels, each channel needs to resolve only about 6 bits of precision, suggesting a scale closer to \(2^6\) per channel in the most favorable balanced picture.

This example is deliberately schematic. The later chapters will replace it with precise assumptions, definitions, and lower bounds. But it already shows why multi-channel encoding matters:

Putting too much precision into one continuous channel can convert saved qubits into exponential query cost. Spreading the precision across several channels can divide the exponent.

The capacity-bound viewpoint

The book’s central result will be developed as a capacity bound. Here, capacity means the amount of distinguishable numerical information that a hybrid encoding can make operationally available under a given query budget.

The word distinguishable is essential. Two mathematical encodings may be different, but if no allowed measurement after \(q\) queries can reliably tell them apart, then the algorithm cannot depend on that difference. In quantum theory, distinguishability is quantified using operational measures such as trace distance and fidelity, which relate quantum states to the best achievable measurement discrimination probabilities (Helstrom, 1976; Nielsen and Chuang, 2010). For parameterized unitaries, distinguishability also connects to quantum Fisher information and metrological resolution bounds (Giovannetti, Lloyd, and Maccone, 2011).

The core law of the book can be previewed informally as follows. Suppose an \(n\)-bit numerical datum must be usable to \(n\)-bit resolution. Suppose \(r\) bits are stored digitally, and the remaining \(n-r\) bits are pushed into \(m\) smooth rotation channels. Under idealized but explicit assumptions—bounded generators, calibrated channels, constant success probability, and a recovery or algorithmic task sensitive to the displaced bits—the query count must scale at least like

\[ q \;\gtrsim\; 2^{(n-r)/m}, \]

up to constants and model-dependent refinements.

This is the intuitive form of the memory–query tradeoff that later chapters will formalize. The book will call its precise version Equation 1. It should be read carefully. It does not say that every algorithm using phase rotations is slow. It does not say that analog control is useless. It does not forbid clever encodings, adaptive measurements, or structured data. Rather, it says that if high-resolution information is not stored digitally, and if the algorithm must nevertheless make that information operationally distinguishable, then the missing resolution reappears as query cost.

In short:

\[ \text{less exact digital memory} \quad\Longrightarrow\quad \text{more required phase resolution} \quad\Longrightarrow\quad \text{more quantum queries}. \]

Why this matters for quantum advantage

The motivation is not only theoretical. Many proposed quantum advantages rely on a favorable scaling in error tolerance. Quantum amplitude estimation is a central example: in the standard ideal model, it can estimate an amplitude to additive error \(\varepsilon\) using \(O(1/\varepsilon)\) oracle calls, whereas classical Monte Carlo sampling typically requires \(O(1/\varepsilon^2)\) samples for comparable root-mean-square accuracy under standard variance assumptions (Brassard et al., 2002; Montanaro, 2015). This quadratic improvement is important in applications such as risk estimation, expectation estimation, and simulation-based finance.

Financial Value-at-Risk is a useful test case. Value-at-Risk asks for a loss threshold associated with a chosen tail probability of a loss distribution. Quantum algorithms for risk analysis have been proposed using amplitude estimation to accelerate probability and expectation estimation in stylized financial models (Woerner and Egger, 2019). But such algorithms need data: distributions, payoffs, correlations, model parameters, and discretizations. If the data-loading strategy saves qubits by hiding precision in a small number of phase rotations, then the resulting query overhead may erase the amplitude-estimation advantage.

This book therefore asks a practical question in a precise way:

When does a hybrid quantum algorithm still beat a strong classical baseline after we include the cost of making its encoded numerical data usable?

The answer depends on the target accuracy, number of digital qubits, number of phase channels, query budget, noise, calibration, and classical comparison point. A claimed quantum advantage is incomplete if it counts the speedup subroutine but ignores the cost of accessing the high-precision data on which that subroutine acts.

The path through the book

The early chapters build the required language. We begin with quantum states, amplitudes, phases, measurement, mixed states, entropy, fidelity, trace distance, and distinguishability. These concepts are not decorative; they are the vocabulary needed to say when two encoded data values can actually be told apart.

We then study numerical data models. A real number can appear as a classical bit string, a quantum basis state, a phase angle, an oracle response, a QRAM-style lookup, or a block-encoded matrix entry. These representations are not interchangeable. Each one makes different promises about memory, control, reversibility, and access cost.

The middle chapters develop the tradeoff itself. Digital qubit storage is exact but memory-intensive. Continuous phase encoding is compact but resolution-limited. Hybrid encoding combines the two. The book then introduces metric entropy, packing and covering numbers, quantum Fisher information, Cramér–Rao-type reasoning, and query lower-bound techniques. These tools lead to the universal capacity bound and its interpretation.

The later chapters turn the bound into design guidance. We examine single-channel slowdown, multi-channel exponent division, optimal allocation across \(r\), \(m\), and \(q\), constructive encoding schemes, decoding and estimation procedures, noise and calibration effects, and integration into larger algorithms. The final application chapters compare the theory against feasibility thresholds for quantum Monte Carlo and financial Value-at-Risk estimation, with attention to whether a proposed advantage survives realistic data-access costs.

The goal is not to discourage hybrid quantum algorithms. The goal is to make them honest, optimizable, and physically meaningful.

A good hybrid encoding is not one that merely stores many digits in a small number of qubits. A good hybrid encoding is one that balances memory and queries so that the algorithm can still use the encoded information within its runtime budget.

That balance is the subject of this book.

References

Brassard, Gilles, Peter Høyer, Michele Mosca, and Alain Tapp. 2002. “Quantum Amplitude Amplification and Estimation.” In Quantum Computation and Information, Contemporary Mathematics 305, 53–74. American Mathematical Society.

Gilyén, András, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2019. “Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204.

Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. 2006. “Quantum Metrology.” Physical Review Letters 96: 010401.

Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. 2011. “Advances in Quantum Metrology.” Nature Photonics 5: 222–229.

Helstrom, Carl W. 1976. Quantum Detection and Estimation Theory. Academic Press.

Holevo, Alexander S. 1982. Probabilistic and Statistical Aspects of Quantum Theory. North-Holland.

Montanaro, Ashley. 2015. “Quantum Speedup of Monte Carlo Methods.” Proceedings of the Royal Society A 471: 20150301.

Nielsen, Michael A., and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.

Woerner, Stefan, and Daniel J. Egger. 2019. “Quantum Risk Analysis.” npj Quantum Information 5: 15.