Source-linked AI summary
A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
Dominik Janzing, Pawel Wocjan, Shengyu Zhang
TL;DR
Measuring arbitrary observables in many-body systems is not straightforward, and measurement complexity is difficult to assess through control-operation lower bounds. This paper constructs a finite-range translationally invariant Hamiltonian for a one-dimensional qudit chain and shows that a single energy measurement on a suitable basis state can yield a quantum circuit's output. The required accuracy scales inverse-polynomially with the circuit's gate count.
Problem
It is not obvious how to measure arbitrary observables in many-component quantum systems, and lower bounds on the control operations needed for measurement are difficult to find.
Source: §1 · pp. 1–2Method
The paper constructs a translationally invariant finite-range Hamiltonian on a one-dimensional qudit chain and encodes a circuit's program and input in a basis state for a single energy measurement.
Source: §1 · pp. 2–3Results
A single measurement of the constructed observable on a basis state has full quantum-computation power, with required accuracy inverse-polynomial in the simulated circuit's gate count.
Source: §6 · pp. 16–17Takeaways & Limitations
The result suggests that realizing energy measurements for real physical systems may be as challenging as realizing quantum computing.
Source: §6 · p. 17For small-constant-k time-independent Hamiltonians, directly implementing an interesting unitary U as exp(−iH) is not known.
Source: §4 · p. 7
Abstract
from arXiv · showhide
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit chain and prove that a single-shot measurement of the energy of an appropriate computational basis state with respect to this Hamiltonian provides the output of any quantum circuit. The required measurement accuracy scales inverse polynomially with the size of the simulated quantum circuit. This shows that the implementation of energy measurements on generic qudit chains is as hard as the realization of quantum computation. Here a ''measurement'' is any procedure that samples from the spectral measure induced by the observable and the state under consideration. As opposed to measurement-based quantum computation, the post-measurement state is irrelevant.
1 Introduction
Measuring arbitrary observables in many-body systems is not straightforward, and determining measurement complexity through control-operation lower bounds is difficult. The paper places the question in complexity theory and shows how a single energy measurement can reveal a quantum computation's output.
1 Introduction
- Quantum information processing can transform observables, but finding lower bounds on the required control operations remains difficult, motivating a complexity-theoretic approach.The paper frames measurement hardness through whether implementing certain measurements would enable classically hard computations.Source: §1 · p. 2
- Earlier measurement-based computation models require concatenated measurements or an entangled initial state, while PSPACE-hard measurement results require exponentially precise resolution.The PSPACE result is about accuracy limits and does not imply that less accurate measurements are also difficult.Source: §1 · p. 2
- The paper extends prior measurement-hardness results [29] from k-local observables to finite-range interactions on one-dimensional chains and translationally invariant operators.The authors characterize these changes as increasing the physical relevance of the result.Source: §1 · p. 2
- The paper further narrows the task to one specific universal observable and a single-shot measurement, rather than repeated measurements of general Hamiltonians.The observable is energy, the Hamiltonian of the system.Source: §1 · p. 3
- A Hamiltonian is constructed so that one energy measurement on an initial basis state reveals the simulated circuit's YES/NO result through disjoint spectra.The initial state encodes the program and classical input; the construction separates the spectra associated with the two outputs.Source: §1 · p. 3
2 Defining measurements and their accuracy
The paper defines measurement by the distribution of outcomes, rather than merely by an expected value, and specifies accuracy and reliability for approximate measurements. It relates this task to phase estimation and to the complexity of implementing measurements.
2 Defining measurements and their accuracy
- A measurement samples eigenvalues of an observable with probabilities given by the state's weights on the corresponding spectral projections.The paper distinguishes this spectral sampling from a procedure that only reproduces the observable's expected value.Source: §2 · pp. 3–4
- Approximate-measurement accuracy is specified by maximal error δ and reliability 1 − ε for outcome probabilities over every interval and state.Outcomes within the interval expanded by δ must occur with probability at least the spectral weight of the original interval times 1 − ε.Source: §2 · p. 4
- For k-local operators on qudits, defining implementation complexity requires specifying elementary operations, such as operations involving two qudits.The cited efficient-simulation statement for time evolution is given for k-local operators on n qubits.Source: §2 · p. 4
- Quantum phase estimation can implement approximate observable measurements with resources polynomial in 1/δ, 1/ε, and the system size n.The construction uses approximations to the unitary evolution generated by the observable.Source: §2 · p. 4
- The paper's hardness result concerns approximate measurements of translationally invariant finite-range qudit-chain Hamiltonians, which can solve PromiseBQP problems.The earlier result [29] established the corresponding complexity for repeated measurements of k-local observables.Source: §2 · p. 4
3 Quantum computation as approximate energy measurement
The paper uses PromiseBQP to describe promise problems solvable by efficient quantum circuits, then constructs a Hamiltonian whose energy measurement simulates such a circuit. The theorem states that an inverse-polynomial-accuracy measurement on a computational basis state can provide the circuit's result.
3 Quantum computation as approximate energy measurement
- PromiseBQP consists of promise problems solvable by a uniform family of quantum circuits, with YES and NO outcomes distinguished under the input promise.The paper uses the promise version because it works with complete problems and BQP is not known to contain a complete problem.Source: §3 · p. 5
- The theorem states that efficient quantum algorithms can be simulated by inverse-polynomial-accuracy energy measurements of finite-range translationally invariant Hamiltonians on a one-dimensional qudit chain.The initial state is a canonical basis state.Source: §3 · p. 6
- The construction defines the j-indexed embedding of V + V† by placing that operator between identity factors in the displayed expression: 1⊗j ⊗(V + V†) ⊗1m−2−j.Source: §3 · p. 6
- For a PromiseBQP circuit family, an efficiently constructible computational basis state and output partition let an energy measurement of H(m) probabilistically decide the problem.The chain size m is polynomial in input length, and the state and partition can be computed efficiently from the input and circuit.Source: §3 · p. 6
4 Spectral requirements on the Hamiltonian
A modified clock evolution yields an energy distribution whose components reflect the circuit’s acceptance probability. Choosing relatively prime clock lengths separates the corresponding spectra, enabling outcome classification from a single sufficiently accurate measurement.
4 Spectral requirements on the Hamiltonian
- The Hamiltonian is formed as H = F + F†, using a forward-time operator F on the data and clock spaces.The construction first relaxes the special Hamiltonian form to clarify the spectral argument before a finite-range translationally invariant construction is supplied later.Source: §4 · pp. 6–7
- A YES computation evolves across a clock chain of length s + 1, whereas a NO computation is restricted to length r + 1.The read-out and annihilation operations make the terminal behavior, and hence the relevant clock-chain length, depend on the computation’s answer.Source: §4 · pp. 7–8
- The energy-measurement distribution is a convex combination of the two line-graph spectral measures, with weights set by the circuit’s acceptance probability.The measures correspond to line graphs of lengths r + 1 and s + 1.Source: §4 · pp. 9–10
- Relatively prime values of r + 2 and s + 2 make the two spectral supports disjoint, allowing single-shot classification rather than repeated sampling.The minimum distance between the transformed eigenvalue sets is at least 1/((r + 2)(s + 2)).Source: §4 · p. 10
- When measurement error exceeds Δ only with small probability, the measurement-based decision procedure essentially reproduces the simulated circuit’s error probabilities.The section establishes that energy measurements for local Hamiltonians can solve PromiseBQP problems, but says this alone does not establish the required nearest-neighbor translationally invariant interaction.Source: §4 · pp. 10–11
5 Construction of the Hamiltonian
The construction encodes circuit layers and data in a quantum cellular automaton (QCA), whose local dynamics simulate the circuit. Its spectral measure can distinguish acceptance outcomes after a single choice of the annihilation-gate position.
5 Construction of the Hamiltonian
- Adjacent S and W gates form the universal circuit set, with disjoint-pair gates grouped into time-step layers.W is applied with its control on the left.Source: §5 · pp. 11–12
5.1 Description of our quantum cellular automaton
- The QCA simulates any such circuit using a number of time steps polynomial in its gate and qubit counts.Source: §5.1 · p. 12
- Local transitions move the program across data cells and execute gates only when program and data are aligned.The transition rules depend on adjacent cells, and alignment determines whether an execution symbol or a hole is created.Source: §5.1 · pp. 13–15
- The two-cell operator V combines program-controlled gate execution X with basis-state transitions T, and the Hamiltonian is built from V and V†.The cell Hilbert space is C56; V acts on two cells.Source: §5.1 · pp. 12, 13, 15
- Circuit layers are encoded as program-code blocks alongside a data band, with the first layer aligned to the register initialized in |x,0⟩.The program band stores the circuit description; the data register represents its logical qubits.Source: §5.1 · pp. 12–13, §5.2 · pp. 15–16
5.2 Spectral properties
- The QCA dynamics form successive clock states, with signal-propagation steps adding polynomial overhead to the simulated circuit.The readout gate’s conditional annihilation also occurs after an extended number of steps.Source: §5.2 · p. 16
- The initial state’s spectral measure under F + F† depends on the circuit’s acceptance probability, and choosing the annihilation-gate position makes the outcome spectra disjoint.The choice makes the extended step counts relatively prime, ensuring the stated minimum spectral separation.Source: §5.2 · p. 16
6 Conclusions
The paper constructs an observable whose single measurement on a basis state has full quantum-computation power, with inverse-polynomial accuracy in the simulated circuit’s gate count. The result concerns a finite-range, translation-symmetric Hamiltonian, although the specific construction is unlikely to occur in real physical systems.
6 Conclusions
- A single measurement of the constructed observable on a basis state has full quantum-computation power, with accuracy inverse polynomial in the simulated circuit’s gate count.Source: §6 · pp. 16–17
- The observable is a finite-range Hamiltonian with translation symmetry, but the authors say their specific construction is unlikely to occur in real physical systems.Source: §6 · p. 17
- The result suggests that implementing energy measurements for real physical systems may be as challenging as realizing quantum computation.Source: §6 · p. 17