Source-linked AI summary
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
TL;DR
The paper asks how to characterize the query complexity of converting between input-dependent quantum states and of evaluating arbitrary functions. It introduces a norm-induced query distance between state families, proves that this distance governs state conversion, and connects it to the general adversary bound. The resulting framework establishes function-composition and discrete/continuous-time query-model results, while bounded-error state conversion retains an error-dependence limitation.
Problem
Quantum query complexity needs a general characterization for converting between input-dependent states and for evaluating functions beyond the boolean-input, boolean-output case.
Method
The paper introduces an information-theoretic norm extending the Schur product operator norm and defines query distance through the Gram matrices of initial and target state families.
Results
The general adversary bound characterizes bounded-error quantum query complexity for any function, while the framework also yields composition and constant-factor equivalence between discrete- and continuous-time query models.
Takeaways & Limitations
The norm-based state-conversion framework unifies function evaluation with broader quantum state transformations and transfers adversary-bound properties to these problems.
Takeaways & Limitations
For general state-conversion problems, error dependence can leave a gap between the theorem’s bounds, and it is unknown whether the dependence can be improved to polylogarithmic in 1/ϵ.
Abstract
from arXiv · showhide
State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.
1 Introduction
The paper formulates state conversion as a norm-based quantum query problem and uses this framework to characterize function-evaluation complexity. It also derives composition and query-model equivalence results from the same characterization.
- Motivation: State conversion is generalized from function evaluation to converting input-dependent states |ρx⟩ into |σx⟩ using queries to x.The framework captures problems such as creating a quantum state for graph isomorphism.
- Core characterization: The complexity of state conversion is characterized by a norm-based distance between the Gram matrices of the initial and target state families.The modified SDP defines the norm, while the query distance is its induced metric.
- Function evaluation: For arbitrary finite-domain and finite-range functions, bounded-error quantum query complexity is characterized by the general adversary bound.The result extends the earlier boolean-input, boolean-output characterization.
- Method: The construction uses an SDP with constraints on all input pairs, whose optimum increases by at most a factor of two over the usual formulation.These additional constraints are crucial for constructing the state-conversion algorithm and extending the framework beyond function evaluation.
- Bounds: The query distance supplies both an algorithmic upper bound and lower bounds for state conversion, with bounded-error lower bounds obtained by optimizing over valid approximate final Gram matrices.The bounded-error condition is related to closeness under the Schur product operator norm.
- Consequences: The adversary bound composes well, while discrete- and continuous-time query complexities are equivalent up to a constant factor in the bounded-error setting.The composition result extends prior boolean-function work, and the model equivalence improves a previously sub-logarithmic-factor relation.
2 Background
State conversion extends function evaluation and state generation by transforming input-dependent quantum states, with coherent and non-coherent output variants. The section introduces the γ2 norm and the notation underlying these problems.
- State-conversion problems: State conversion generalizes state generation, which in turn generalizes function evaluation.
- Coherent and non-coherent variants: Coherent and non-coherent variants differ in their output conditions while both allow workspace.
- Coherent and non-coherent variants: For function evaluation, coherent and non-coherent complexities agree up to constant factors, but phase computation separates them sharply.For targets |σx⟩ = (−1)^f(x)|0⟩, non-coherent complexity is trivial while bounded-error coherent complexity equals Q(f) up to constants.
- The γ2 norm: The γ2 norm, also called the Schur product operator norm, is used as a central quantum-information-theoretic tool.The section introduces matrix notation, including Schur products, spectral norms, identity matrices, all-ones matrices, and Kronecker deltas.
3 Filtered γ2 norm and query distance
The filtered γ2 norm measures state-conversion difficulty through query-sensitive filters. Its induced query distance connects state conversion to the general adversary bound and differs from it by at most a factor of two.
- Filtered γ2 norm: The filtered γ2 norm generalizes γ2 by filtering matrix factorizations through a set of matrices.
- Query distance: The query filters Δ_j encode whether a query to index j distinguishes inputs x and y.
- Query distance: The query distance between Gram matrices ρ and σ is γ2(ρ − σ|Δ), the metric induced by the query process.
- Connection to the adversary bound: The query distance characterizes the quantum query complexity of state conversion and is closely related to the general adversary bound.
- Connection to the adversary bound: The adversary bound omits constraints for equal-output input pairs, whereas the filtered norm imposes constraints on all pairs.The additional constraints raise the optimum by at most a factor of two and are important for algorithm construction and state-conversion extensions.
- Connection to the adversary bound: The general adversary bound and γ2(J − F|Δ) differ by at most a factor of two and coincide for boolean-output functions.
4 Characterization of quantum query complexity
The section characterizes state-conversion query complexity using an SDP-derived norm and an algorithm based on phase detection and repeated reflections. It also establishes matching lower-bound machinery, discusses error dependence, and proves equivalence of continuous-time and discrete query models.
- The query complexities of function evaluation and coherent and non-coherent state conversion are characterized using γ2 and γ2(·|∆).
- The algorithm converts |ρx⟩ to a high-fidelity approximation of |σx⟩ using a number of queries governed by the query distance between their Gram matrices.The construction uses a phase-detection procedure applied to a product of two reflections.
- The effective spectral gap lemma analyzes the product of two reflections and provides the central correctness argument for the conversion algorithm.The proof uses projections and reflections, with phase detection approximately reflecting components associated with small eigenphases.
- The query-distance norm supplies lower bounds for exact and bounded-error state conversion through output conditions on valid final Gram matrices.For exact conversion, one query implies γ2(ρ −σ|∆) ≤2; bounded-error bounds minimize the distance over admissible σ′.
- General state-conversion characterizations can have an error-parameter gap because the problems need not satisfy the robustness condition used in the functional case.The authors do not know whether the algorithm’s ϵ-dependence can be improved to polylogarithmic in 1/ϵ.
- The bounded-error continuous-time and discrete query models are equivalent, including for general state-conversion problems.
5 Function composition
The paper studies how the general adversary bound behaves under function composition. It proves an upper bound for arbitrary finite functions, a matching lower bound when the inner function is Boolean, and corresponding direct-sum consequences.
- Composition setup: Function composition is defined by applying g independently to input blocks and then applying f to the resulting outputs.The construction maps n blocks through g before evaluating f on the n outputs.
- Upper bound: Adv±(f ◦ g^n) ≤ Adv±(f) γ2(J − G|∆) for arbitrary finite functions.The bound follows by tensoring optimal solutions for the Adv±(f) and filtered γ2(J − G|∆) programs.
- Upper bound: The upper-bound proof relies on the extra constraints in the filtered γ2 program, which are unavailable in the same direct form for the general adversary program.The paper identifies the bound as a special case of a more general filtered γ2 inequality.
- Lower bound: A matching lower bound is not always available for arbitrary output ranges, because composition can become constant even when the component functions are nonconstant.The paper gives the example of an inner function outputting only even numbers and an outer parity function.
- Lower bound: When g has Boolean range, Adv±(f ◦ g^n) ≥ Adv±(f)Adv±(g), matching the composition upper bound in the Boolean setting.For Boolean inputs and outputs, the paper notes that the matching lower bound was previously known.
- Direct sums: The composition lemmas also yield direct-sum results for n independent copies of a function, including an adversary-bound upper bound of n Adv±(g).The corresponding lower bound had been established previously, and Theorem 1.1 transfers the adversary characterization to query complexity.
A Properties of the filtered γ2 norm
This appendix develops algebraic and optimization properties of the filtered γ2 norm. These properties establish that it is a norm on the relevant support and behaves predictably under matrix operations, filtering, and tensor products.
- SDP formulations: The filtered norm has equivalent primal and dual semidefinite formulations, with equality under the stated strict-feasibility condition.The appendix gives a trace-minimization form and invokes SDP duality to establish attainment and equality.
- Norm properties: The filtered γ2 quantity is a norm when its matrix arguments are supported on the union of the filter supports.Its proof uses positivity, homogeneity, and the triangle inequality derived from vector solutions.
- Norm properties: γ2(A|Z) is zero only for A = 0 and is infinite exactly when a nonzero entry of A is uncovered by every filter matrix.This characterizes when the filtered program is feasible.
- Invariances: The norm is positively scalable, invariant under duplicating corresponding rows or columns, and nonincreasing when additional filter matrices are included.Adding a filter that is a rectangular restriction of an existing one does not change the value.
- Filter operations: Disjoint filter supports can be merged without changing the filtered γ2 value.The proof concatenates vector solutions and then separates them according to the nontrivial rows and columns of each support.
- Composition properties: Filtered γ2 is submultiplicative under matrix products and exactly multiplicative under tensor products with tensor-product filters.The tensor-product identity is established using both primal vector solutions and dual SDP solutions.
B Application to continuous-time query complexity
The paper connects continuous-time query complexity to fractional queries and uses the filtered γ2 norm to control state changes under fractional queries. This supports equivalence of the continuous-time and discrete query models up to constant factors.
- Model equivalence: The continuous-time query model is equivalent to the fractional quantum query model up to constant factors.This equivalence is the first step in the cited proof strategy for continuous-time query complexity.
- Conclusion: The filtered γ2 lower bound, together with the corresponding upper bound, yields the continuous-time query-complexity theorem.The passage explicitly connects the lower-bound argument to Theorem 4.10.
- Fractional queries: A λ-fractional query applies phase e^{iλπx_i} to the query register, has cost λ, and recovers the usual query when λ = 1.The fractional model is described for Boolean input in this section.
- Fractional queries: A single λ-fractional query changes the filtered γ2 distance by at most λπ.This lemma supplies the lower-bound step for fractional query complexity.
- Proof construction: The proof constructs positive semidefinite matrices P_j whose sum represents the Gram-matrix difference ρ − σ.The construction uses auxiliary matrices M_j and E_j and a parameter λ.
C Function composition
The appendix proves the function-composition lemmas by constructing feasible adversary solutions from optimal solutions for the component functions. The construction uses lifted matrices, tensor products, and Boolean-specific structure.
- Setup: For composition, the proof lifts matrices from g's domain to block inputs and defines filtering matrices for each inner and outer query position.The lifted matrix ˜A replaces entries indexed by transformed inputs, while ∆(p,q) identifies the relevant block and inner query.
- Lower-bound construction: The lower-bound proof uses the dual formulation of the adversary bound and structural properties of an optimal dual solution.For Boolean-valued g, the proof additionally exploits the block structure obtained by grouping inputs according to g's output.
- Boolean case: Boolean functions supply the key special property used in the lower-bound argument.The appendix explicitly identifies this as the main property of Boolean functions used in the proof.
- Upper-bound construction: The upper-bound proof represents the composed adversary solution using a tensor product of the outer solution and inner-function solution matrices.The proposed solution combines ˜Λ ◦ Ω^⊗n with a weight matrix built from ˜V and (d_gΩ + W)^⊗n.
- Upper-bound construction: The constructed weight matrix satisfies the required zero constraint because the corresponding constraint holds for the outer adversary solution.The proof uses F ◦ V = 0 to establish the lifted constraint.
- Feasibility: Feasibility follows from positive semidefiniteness of the component matrices and identities relating the lifted filters to the inner adversary constraints.The proof verifies the composed semidefinite constraints for every pair (p,q).