Block encoding and qubitization

Short answer: A block encoding embeds a matrix inside a larger unitary operation so that the matrix appears as a sub-block, and qubitization is a technique that uses such encodings to simulate Hamiltonian time evolution. A 2019 paper in Quantum reports that its algorithm approximates the time-evolution operator with a number of queries that grows as t plus log(1/error), which it says is optimal in all parameters. This is algorithm theory, not a hardware result.

Block encoding

A set of 2023 lecture notes from a university course defines a block encoding of a matrix M acting on n qubits with m ancilla qubits as a unitary A acting on m plus n qubits in which M is the top-left block. The notes say the Hamiltonian simulation problem was one of the initial motivations behind the quantum computer. A page in the documentation of a quantum software company, Classiq, describes a block-encoded Hamiltonian as one embedded within a larger unitary matrix. That page is vendor documentation, so treat its comparisons as that company's description.

What the 2019 paper presents

The Quantum paper addresses approximating the time-evolution operator for a Hamiltonian H to a given error. It takes H to be the projection of a unitary oracle onto a state created by another unitary oracle. Its algorithm has a query complexity of order t plus log(1/error) to both oracles, which the authors say is optimal with respect to all parameters in both the asymptotic and non-asymptotic regimes, and with low overhead, using at most two additional ancilla qubits.

The authors say this approach subsumes important prior work on Hamiltonians that are d-sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. They also say it motivates new instances, such as where H is a density matrix.

Qubitization

The paper calls its key technical result qubitization. It uses the controlled versions of the oracles to embed any H in an invariant SU(2) subspace. A large class of operator functions of H can then be computed with optimal query complexity, of which the time-evolution operator is a special case, according to the authors.

An implementation-oriented description

The Classiq page describes the task as taking a Hermitian operator H given through a block-encoding unitary, with a scaling factor at least as large as the norm of H, an evolution time and a target error, and producing a unitary that approximates the time-evolution operator within that error. It says qubitization combines the Jacobi-Anger expansion with the linear combination of unitaries technique, and that powers of the walk operator implement Chebyshev polynomial block-encodings. It says this needs no classical preprocessing for rotation angles but uses more ancilla qubits, of order log d for polynomial degree d, than two other methods it names, GQSP and QSVT.

The lecture notes state a theorem of the same kind: from a block encoding of a Hermitian H with the norm bounded by 1, they obtain a block encoding of a matrix close to the time-evolution operator using O(t + log(1/error)) controlled applications of the black box and its inverse, and note that the number of applications is optimal up to a constant factor.

What this does not tell you

These sources are theory papers, lecture notes and one vendor documentation page. They do not report running qubitization on a quantum computer, and they say nothing about the size of a machine needed for a useful problem. Query complexity counts calls to oracles, not wall-clock time or hardware cost.

FAQ

What is a block encoding?

A unitary on more qubits in which a chosen matrix appears as a sub-block, per the lecture notes.

What is qubitization?

The 2019 paper's key technical result: using controlled oracles to embed a Hamiltonian in an invariant SU(2) subspace so functions of it can be computed with optimal query complexity.

How many queries does it need?

The paper reports a number of order t plus log(1/error), and says this is optimal.

Does it need many ancilla qubits?

The 2019 paper says at most two additional ancilla qubits. A vendor page describes a Chebyshev-based variant that uses order log d ancillas.

Has it been run on hardware?

These sources do not report that.