Formalize Open Quantum Problem #16: Complexity of product preparations

### What is the conjecture

This is problem [#16](https://oqp.iqoqi.oeaw.ac.at/complexity-of-product-preparations) in [Reinhard F. Werner’s collection](https://arxiv.org/abs/quant-ph/0504166), later [collected by a community of quantum researchers](https://oqp.iqoqi.oeaw.ac.at/open-quantum-problems).

> **Problem (Open Quantum Problem #16: “Complexity of product preparations”).**
> Let `|ψ⟩` be a pure state on `m` qubits. How does the cost of preparing `|ψ⟩^{⊗ n}` grow with `n`, compared with the cost of preparing a single copy of `|ψ⟩`?
>
> Here, “algorithmic complexity” means the total gate cost of a circuit that maps the all-zero input state to the target state.
>
> The answer depends on the allowed gate model, so the problem is really about asymptotic scaling for a fixed gate set. A model suggested in the original statement uses gates of the form `exp(i φ σ_u)`, where `σ_u` is a Pauli-string operator, with gate cost `|φ|`.
>
> One can also formulate an approximate version with an error parameter.

A standard formalization is in terms of **state-preparation complexity**:

* Fix `m,n ≥ 1` and a known pure state `|ψ⟩ ∈ (ℂ^2)^{⊗ m}`.
* Fix a gate model `G`. Following the OQP statement, one natural choice is the continuous gate set consisting of Pauli-product rotations `exp(i φ σ_u)`, where `σ_u` is any tensor product of Pauli matrices and the cost of the gate is `|φ|`.
* Define the exact preparation cost
`C_G(|ψ⟩) := inf { total gate cost of a circuit taking |0^m⟩ to |ψ⟩ }`.
* Define the `n`-copy / product-preparation cost
`C_G^{(n)}(|ψ⟩) := C_G(|ψ⟩^{⊗ n})`,
i.e. the minimum cost to prepare `|ψ⟩^{⊗ n}` on `mn` qubits from `|0^{mn}⟩`.

A trivial baseline upper bound is:

* `C_G^{(n)}(|ψ⟩) ≤ n C_G(|ψ⟩)`,
by preparing each copy independently with an optimal single-copy circuit.

The actual open problem is to understand the asymptotic relation between these quantities:

* **Main question / open asymptotic problem:** characterize or tightly bound `C_G^{(n)}(|ψ⟩)` as a function of `n`, `m`, and `C_G(|ψ⟩)`.

A natural approximate variant is:

* For `ε > 0`, define `C_{G,ε}(|ψ⟩)` to be the minimum cost to prepare a state within error `ε` of `|ψ⟩` (for some chosen metric, e.g. trace distance / purified distance / infidelity).
* Define `C_{G,ε}^{(n)}(|ψ⟩) := C_{G,ε}(|ψ⟩^{⊗ n})`.
* Then ask for the optimal asymptotic dependence on `n`, `m`, `ε`, and `C_{G,ε}(|ψ⟩)`.

The original Werner/Krüger version also records the guiding remark:

* Because `|ψ⟩` is known, producing many copies might conceivably be asymptotically cheaper than preparing the state from scratch each time.

So another equivalent way to phrase the problem is:

* **Direct-product / state-dependent cloning viewpoint:** the circuit is allowed to depend on the target state `|ψ⟩`; the question is whether state-specific preparation of `|ψ⟩^{⊗ n}` can asymptotically outperform repeating an optimal single-copy preparation `n` times.

A useful extremal formulation for formalization is:

* For fixed `m` and `k`, define
`F_G(n,m,k) := sup { C_G(|ψ⟩^{⊗ n}) : |ψ⟩ ∈ (ℂ^2)^{⊗ m}, C_G(|ψ⟩) ≤ k }`.
* Then ask for the asymptotic growth of `F_G(n,m,k)` as a function of `n,m,k`
(and analogously for the approximate version).

### Where to find the details / references

Primary sources:

* [Open Quantum Problems site (Problem #16)](https://oqp.iqoqi.oeaw.ac.at/complexity-of-product-preparations)
* [Open Quantum Problems master list (for numbering/metadata)](https://oqp.iqoqi.oeaw.ac.at/open-quantum-problems)
* O. Krüger & R. F. Werner, “Some Open Problems in Quantum Information Theory” (Problem 16):
[https://arxiv.org/abs/quant-ph/0504166](https://arxiv.org/abs/quant-ph/0504166)
[https://arxiv.org/pdf/quant-ph/0504166](https://arxiv.org/pdf/quant-ph/0504166)

Key related references:

* E. Knill, “Approximation by quantum circuits” (arXiv: quant-ph/9508006)
(background on gate-count / approximation complexity for state and unitary preparation)
* C. Mora & H. J. Briegel, “Algorithmic complexity and entanglement of quantum states” (Phys. Rev. Lett. 95, 200503 (2005); arXiv: quant-ph/0505200)
(systematic definition of quantum state algorithmic complexity with a precision parameter)
* M. Plesch & Č. Brukner, “Quantum-state preparation with universal gate decompositions” (Phys. Rev. A 83, 032302 (2011); arXiv: 1003.5760)
(explicit upper bounds for general pure-state preparation circuits)
* R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, “Quantum circuits for isometries” (Phys. Rev. A 93, 032318 (2016); arXiv: 1501.06911)
(near-optimal circuit-synthesis results for state preparation as an isometry problem)
* V. Scarani, S. Iblisdir, N. Gisin, and A. Acín, “Quantum cloning” (Rev. Mod. Phys. 77, 1225–1256 (2005); arXiv: quant-ph/0511088)
(broad review of cloning literature; the Werner/Krüger entry explicitly notes that optimal cloning literature is relevant)

### Prerequisites needed

* Finite-dimensional quantum mechanics: pure states, qubits, tensor products, tensor powers `|ψ⟩^{⊗ n}`
* Quantum circuits / state preparation: circuit semantics, gate counts or weighted gate costs, asymptotic complexity notions
* Linear algebra / matrix analysis: unitary operators, Pauli matrices, operator exponentials `exp(i φ σ_u)`
* (For the approximate version) distance measures on states, such as fidelity / infidelity or trace distance
* (Optional) cloning/state-preparation background, including the distinction between universal no-cloning and state-specific preparation of a known target state

### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)

* ams-81 (Quantum theory)
* ams-68 (Computer science)
* ams-94 (Information and communication theory)

### Choose either option

* [ ] I plan on adding this conjecture to the repository
* [x] This issue is up for grabs: I would like to see this conjecture added by somebody else

---

Start by reading the Open Quantum Problems entry for Problem #16 and the cited Krüger–Werner paper, then review the repository's existing conjecture formalizations. The payload names no target file, entry point, or formal statement, so the work is done only when the conjecture has been made precise and added in Lean with an appropriate repository structure.

Written by the indexing model from the issue text.