Quantum circuit
“A quantum circuit is a unitary U. Parametrized by a depth t: U = Uₜ … U₁ where Uⱼ is unitary on (ℂ²)^⊗n and Uⱼ = ⨂ i, Uⱼᵢ is a tensor product of disjoint two-qubit unitaries Uⱼᵢ.
/-- Definition 3.1: circuit complexity of quantum state -/
def complexity (ρ : quantum_state n) :
min { depth over all n'-qubit circuits U | U |0⟩^⊗n' is a purification of ρ }
def trivial (A family of states {𝜌 𝑛} for growing 𝑛) :
∀ n, ∃ c, complexity(ρ 𝑛) ≤ c
-- Product states are instance of trivial, low-depth states.
“Lightcones For an operator A (think of A as a projector onto a single qubit) and a circuit U, let the lightcone of A, with respect to U, be the set of qubits on which UAU† acts non-trivially. For a qubit i, let the lightcone of qubit i be the union of lightcones over all operators A supported on qubit i.”
”
/-- Fact 3.2 -/
theorem For a circuit U of depth t, the size of the lightcone of qubit i is ≤ 2ᵗ :=
begin
Uᵢ...U₁ A U₁† ... Uᵢ acts non-trivially on at most 2ⁱ qubits, since each Uᵢ is the tensor product of 2 qubit unitaries.
end
”
Trivial states and local Hamiltonians
| “The 0-depth state | 0𝑛’⟩ is the ground state of the 1-local Hamiltonian H₀ = ∑ i, | 1⟩⟨1 | ᵢ. |
| The Hamiltonian H₀ is frustration-free. Has a unique ground state of | 0𝑛’⟩. Is commuting. And has a spectral gap of 1. The eigenvectors are all | x⟩ for x ∈ {0, 1}𝑛’ with eigenvalues | 𝑥 | . |
| For any circuit U on 𝑛’ qubits of depth t, we can consider the Hamiltonian Hᵤ = ∑ i, U | 1⟩⟨1 | ᵢU† |
| Since U is a unitary, the analysis of H₀ directly translates to Hᵤ: it is frustration-free, has a unique ground state of U | 0𝑛’⟩, is commuting, and has a spectral gap of 1. The eigenvectors are all the vectors U | x⟩ for x ∈ {0,1}𝑛’ and their respective eigenvalues are | x | . |
Furthermore, by Fact 3.2, the Hamiltonian Hᵤ is 2t-local. This underlines the fundamental relationship between trivial states and local Hamiltonians.
Fact 3.12
theorem unique_ground_of_trivial :
Every trivial state |𝜓⟩ ∈ (ℂ²)⊗n'
is the unique ground state
of a 𝑂(1)-local frustration-free commuting Hamiltonian with spectral gap 1.
/- Definition 3.13: δ-approximate ground state projector -/
def approx_ground_state_projector (H : Hamiltonian) [frustration_free H] [unique_gound_state H |Ω⟩] (K : operator) (δ : ℝ) :=
∥|Ω⟩⟨Ω| − K∥ ≤ δ
We can see that (I − Hᵤ/n’) is a (1−1/n’)-AGSP for Hᵤ since 1 is the spectral gap of the Hamiltonian Hᵤ. It follows that polynomials (I − Hᵤ/n’)^𝑓 are better AGSPs at the cost of locality: They are roughly (1 − 𝑓/n’)-AGSPs but are 𝑓 · 2𝑡 -local. Is there an optimal polynomial of I − Hᵤ which maximizes the quality of the AGSP without sacrificing locality?
Lemma 3.14 (Optimal polynomial approximation to the AND function [60])
lemma : ∃ polynomial P of degree f ∈ (√n', n') such that P(0) = 1 ∧ ∀ i > 0, |P(i)| ≤ exp(-f²/(100n'))
A construction of 𝑃 can be built using Chebyshev polynomials. By construction, P(Hᵤ) will be a exp(− 𝑓 2100𝑛’)-AGSP with a locality of 𝑓 · 2𝑡 . Therefore, states of depth 𝑂 (log 𝑛) are the ground states of very good AGSPs of locality 𝑜(𝑛). This comes in handy in proving circuit depth lower bounds.”
“Local indistinguishability and circuit depth”
| “For every [[n, k, d]] quantum error correcting code, any codeword ρ and any subset 𝑆 ⊂ [𝑛], | 𝑆 | ≤ 𝑑, it holds that ρ𝑆 is an invariant over the code space. |
This is an example of a more general property called local indistinguishability. Used to prove circuit depth lower bounds.
def d_locally_indistinguishable (d : ℕ) (ρ φ : quantum_state n) :=
∀ S ⊂ [n], |S| ≤ d, ρS = φS
| Another example of locally indistinguishable states: GHZₙ = ( | 0ⁿ⟩ ± | 1¹⟩)/√2. The ± phase can only be recognized by viewing all n qubits. For less than n qubit the reduced density matrix in either case is ( | 0⟩⟨0 | _ | S | + | 1⟩⟨1 | _ | S | )/2. |
The complexity of generating GHZₙ₊ comes from the long-range correlations between all n qubits. We can prove a simple circuit depth lower bound.
lemma simp_loc_indistinguishability (d : ℕ) (ρ φ : quantum_state n) [pure ρ φ] :
d_locally_indistinguishable d ρ φ → complexity ρ > Ω(log n) ∧ complexity φ > Ω(log n) :=
begin
by contradiction,
Assume ∃ U of depth t, |ρ⟩ = U |0𝑛⟩ with t < d/2.
Consider the Hamiltonian Hᵤ from earlier; its unique ground state will be |ρ⟩ and it is 2𝑡 -local.
Let hᵢ = U |1⟩⟨1|𝑖 U† be the local terms of Hᵤ; therefore ℎ𝑖 acts non-trivially only on lightcone Lᵢ.
Then ... where both equality equations (★) follow from the fact that the energy of the term hᵢ only depends on the reduced density matrix state on the lightcone Lᵢ and the equality equation (†) follows because the size of the lightcones Lᵢ are at most 2𝑡 < 𝑑 and therefore 𝜑Lᵢ = ρLᵢ by local indistinguishability.
Therefore, |𝜑⟩ is a ground state of H𝑈 implies that it equals |ρ⟩, a contradiction.
So, 2𝑡 ≥ 𝑑, proving the lower bound.
end
/-- H cannot distinguish ρ and φ -/
theorem (d : ℕ) (ρ φ : quantum_state n) [pure ρ φ] (H : Hamiltonian) [d_local d H] :
d_locally_indistinguishable d ρ φ → d_local H → ⟨ρ|H|ρ⟩ = ⟨φ|H|φ⟩
| States | GHZ±⟩ are (n − 1)-locally indistinguishable. So from the theorems above follows a circuit depth lower bounds of Ω(log n). |
It also gives a Ω(log d) lower bound for pure codewords of a [[n, k, d]] code where k ≥ 1. Because two orthogonal codewords are d-locally-indistinguishable (Fact 2.1).
Can we find a more robust lemma? For mixed states. And states not exactly equal to ρ but in its δ-neighborhood.”
| “The lower bound for | GHZ+⟩ implies a Ω(log n) lower bound for the probability distribution with half its mass on 0𝑛 and the other half on 1𝑛.” |
What is it hard to make a circuit whose output measures 00000… half of the time and 11111…. half of the time?
Generalize: D(0𝑛), D(1𝑛) = 1/2 to D(0𝑛), D(1𝑛) ≥ μ.
Generalize: D(0𝑛), D(1𝑛) ≥ μ to D(S₁), D(S₂) ≥ μ for sets S₁ and S₂.
For S₁ and S₂ separated by a large Hamming distance D is called a “well-spread” distribution.
/-- Lemma 3.18
"D generated by measuring the output of a quantum circuit in the standard basis"
This lemma applies to mixed states -/
lemma circ_depth_3_18 (D : prob_dist on {0, 1}ⁿ) (S₁ S₂ ⊂ {0, 1}ⁿ) :
D(S₁) ≥ μ ∧ D(S₂) ≥ μ → circuit_depth ≥ 1/3 * log (Hamming_dist(S₁,S₂)²/(400n * ln(1/μ))) :=
begin
sorry
end
| “Simple observation: Take an l-local operator h. And basis vectors | x⟩, | y⟩ for x, y ∈ {0, 1}ⁿ. With Hamming distance | x ⊕ y | > l. Then ⟨x | h | y⟩ = 0. Therefore, for sets S₁ and S₂ any local operator H of locality < dist(S₁,S₂), Π𝑆1 H Π𝑆2 = 0 where ΠS₁, ΠS₂ are the projections on the strings in sets S₁,S₂, respectively |
Lemma 3.18 provides a non-trivial lower bound only when Hamming_dist(S₁,S₂) ≥ ω(√n). This is fine in some cases we can consider a restriction of the distribution to fewer bits to reduce n while still preserving the distance.
But how to use Lemma 3.18 to lower bound the circuit depth of codewords of ALL quantum codes?
We can use Lemma 3.18 to lower bound the circuit depth of codewords of CSS codes (and any state within small 1-distance of the code space) for d ≥ ω(√n).”
-
“A proof sketch of Lemma 3.18 through the lens of local indistinguishability:
-
Recall, we are interested in lower bounding the circuit depth of any state ρ⟩ on n’ qubits such that measuring ρ⟩ in the standard basis yields the distribution D. -
To apply Lemma 3.16, we would need to create a state 𝜑⟩ with the same reduced density matrices. - Instead, we create a state with approximately the same reduced density matrices.”
-