Source-linked AI summary
Efficient Representation of Quantum Many-body States with Deep Neural Networks
Xun Gao, Lu-Ming Duan
TL;DR
The paper asks how the representational power of deep and shallow neural networks differs for quantum many-body states. It develops rigorous representation and no-go proofs, showing that DBMs can efficiently represent broad state classes while RBMs cannot represent certain states under complexity-theoretic assumptions.
Problem
The paper examines what characterizes the representational power of deep versus shallow neural-network representations of quantum many-body states.
Method
The paper constructs DBM representations by simulating fully connected Boltzmann machines with interaction gadgets and proves RBM limitations for selected entangled states.
Results
The authors prove that DBMs efficiently represent ground states of k-local Hamiltonians, while RBMs cannot efficiently represent the GWD state under stated complexity-theoretic assumptions.
Takeaways & Limitations
The results establish distinct representational capabilities for deep and shallow Boltzmann-machine architectures within the studied quantum-state classes.
Takeaways & Limitations
The approximate-representation no-go result depends on a conjecture about average-case hardness of approximating the state amplitudes.
Abstract
from arXiv · showhide
The challenge of quantum many-body problems comes from the difficulty to represent large-scale quantum states, which in general requires an exponentially large number of parameters. Recently, a connection has been made between quantum many-body states and the neural network representation (\textit{arXiv:1606.02318}). An important open question is what characterizes the representational power of deep and shallow neural networks, which is of fundamental interest due to popularity of the deep learning methods. Here, we give a rigorous proof that a deep neural network can efficiently represent most physical states, including those generated by any polynomial size quantum circuits or ground states of many body Hamiltonians with polynomial-size gaps, while a shallow network through a restricted Boltzmann machine cannot efficiently represent those states unless the polynomial hierarchy in computational complexity theory collapses.
METHODS
The methods show that fully connected Boltzmann machines can be efficiently simulated by deep Boltzmann machines without intra-layer connections. This construction uses a hidden-neuron gadget whose parameters reproduce a two-neuron interaction.
- DBM simulation: A hidden-neuron gadget simulates interactions between two neurons, enabling efficient simulation of fully connected Boltzmann machines by DBMs without intra-layer connections.The construction applies to fully connected Boltzmann machines with intra-layer edges.
- Parameter construction: Three equations constrain gadget parameters a, b, c, and d so the hidden-neuron expression reproduces the interaction term Jx_1x_2.The constraints are ea cosh(c) = 1, eaed cosh(b + c) = 1, and eae2d cosh(2b + c) = eJ.
- Parameter construction: One solution is a = −d = −J/2 and b = −c = −i arccos(eJ/2).This parameter choice is given as equation (8).
Detailed derivation of the weight functions WH and Wθ
This section derives the weight functions WH and Wθ by assuming a general bilinear form and solving the resulting equations. It applies this procedure to Hadamard and phase gadgets used in RBM gate simulations.
- General derivation: WH and Wθ are derived by setting each weight function to a+bx+ch+dxh and solving the resulting parameter equations.This general ansatz provides the starting point for the detailed derivation.
- Hadamard gadget: The Hadamard gadget requires solving an equation for the RBM representation of graph states and the simulation of H and CZ gates.The derivation uses this gadget-specific constraint to determine the Hadamard weights.
- Hadamard gadget: WH (xi,h) is given explicitly as iπxih −iπ [2xi + h] /4 + (iπ/4 −ln 2) /2 for xi equal to x1 or x2.The expression supplies the weight assigned to either input variable in the Hadamard gadget.
- Phase gadget: The phase gadget imposes a separate equation to simulate the Z(θ) gate.The derivation notes the identity δx1x2eiθx1 = δx1x2eiθ(x1+x2)/2 before obtaining the solution.
RBM representation of many-body entangled states
A simple RBM gadget with one hidden neuron and identical edge weights represents several highly entangled states. These include the toric code, volume-law entangled-pair states, and coherent thermal states describing critical systems.
- RBM gadget: The construction restricts to one hidden neuron connected to k visible neurons with an identical weight function W on every edge.The weights are chosen by solving an equation for a specified correlation function g(v1, · · ·, vk).
- Entangled-state classes: The construction represents three entangled-state classes: the toric code, randomly distributed entangled pairs, and coherent thermal states.These cover topological order, volume-law entanglement, and critical-system behavior, respectively.
- Toric code: For the toric code, the RBM uses the weight W(vi, h) = iπvih −(ln 2) /4 and is significantly simpler than another published construction.Its local correlation is g(v1, v2, v3, v4) = (v1 + v2 + v3 + v4 mod 2), with the wave function formed as a product over vertices.
- Entangled pairs: Randomly distributed entangled pairs use g(v1, v2) = δv1v2 for each |00⟩+ |11⟩ pair, with W(vi, h) given by the identity phase gadget Wθ at θ = 0.These states satisfy an entanglement volume law instead of an area law.
- Coherent thermal state: At β = βc, the coherent thermal state |Ψch⟩ describes a many-body entangled critical system in the 2D Ising model.For any β, its wave function can be simply represented, and its correlation function matches that of the corresponding thermal state.
Proof of theorem 1 under approximation representation
The section introduces the 2D-lattice state |ψGWD⟩, obtained from a cluster state by one layer of translation-invariant single-qubit unitaries. It proves that RBMs cannot efficiently represent this state, exactly or approximately, under reasonable complexity-theoretic conjectures.
- State construction: The 2D-lattice state |ψGWD⟩ is a cluster state after one layer of translation-invariant single-qubit unitary transformation.The state was introduced in Ref. [18] for proving quantum supremacy.
- No-go theorem: RBMs cannot efficiently represent |ψGWD⟩ under reasonable conjectures in complexity theory, for both exact and approximate representation.The result is presented as a no-go theorem for this specific state.
Exact representation
The section argues that approximating computational-basis amplitudes of the state |ψGWD⟩ is #P-hard. Efficient RBM representation would place these computations in P/poly, implying a polynomial-hierarchy collapse considered unlikely.
- Exact representation: Approximating |Ψ(v)|² for |ψGWD⟩ in the computational basis is #P-hard under the stated estimation condition.Here, |Ψ(v)|² corresponds to q_x in Ref. [18].
- Exact representation: An oracle computing the first mn −1 digits of Ψ(v) is introduced to connect amplitude computation with the hardness result.
- Exact representation: If |ψGWD⟩ has an efficient RBM representation, its computational-basis wave function belongs to P/poly, yielding O ⊆ P/poly.
- Exact representation: The resulting containment would collapse the polynomial hierarchy, an outcome widely believed to be unlikely.
Approximate representation
The section develops an average-case hardness argument for approximate RBM representation based on Conjecture 1. Under this conjecture, achieving trace distance below ϵ/2 would collapse the polynomial hierarchy.
- Average-case hardness: Conjecture 1 asserts that approximating |Ψ(v)|2 by |eΨ(v)|2 within the specified error remains #P-hard for any 1 −δ fraction of instances.The conjecture lifts the hardness assumption from worst-case to average-case instances.
- Average-case hardness: The conjecture is motivated by classical hardness for simulating random quantum-circuit distributions, quantum chaos theory, and extensive numerical simulations.These arguments are presented as support for the conjecture rather than as a proof of it.
- Hardness of RBM approximation: If Conjecture 1 holds, any RBM state has trace distance at least ϵ/2 from |ψGWD⟩ unless P#P ⊆ PP/poly and the polynomial hierarchy collapses.The result rules out efficient approximation by RBM states under the stated complexity-theoretic assumption.
Efficient tensor network representation for ground states
The section constructs ground states of k-local Hamiltonians using a truncated Taylor expansion of imaginary-time evolution, yielding efficient tensor-network and DBM representations. The required representation size scales polynomially with system parameters, energy gap, and target precision.
- Construction: The construction approximates e^(-βH) with a Taylor expansion truncated at order K, using O(Km) elementary pseudo quantum gates.The Hamiltonian has m interaction terms, and the truncation order is K.
- Error control: The approximation error combines suppression of excited states by e^(-β∆) with Taylor-series truncation error.The target ground state is the first term, while the two remaining contributions determine the required β and K.
- Efficiency: O(Km) elementary tensors represent the Hamiltonian ground state, with each tensor having constant bond dimension D and typically small coordination number d.This yields an efficient tensor-network representation for the ground state.
- DBM representation: The tensor-network construction directly gives a DBM representation with the same total number of neurons by theorem 3.The resulting neuron count is the same as the elementary-tensor count used for the ground-state representation.