Quantum Inference on Bayesian Networks

I. INTRODUCTION

• Bayesian inference supports rational decision-making and applications including system modeling, model learning, data analysis, and decision making.A partially observable Markov decision process is described as a special case of a Bayesian network.Source: §I · p. 1
• Classical rejection sampling takes O(nmP(e)^-1) time per sample because it discards samples with incorrect evidence.The evidence probability P(e) can become exponentially small as the number of evidence variables grows.Source: §I · p. 1
• Quantum rejection sampling had previously shown an oracle-relativized square-root speedup, but assumed a state-preparation oracle whose efficient implementation is not guaranteed.Preparing arbitrary states can encode witness generation for QMA-complete problems.Source: §I · pp. 1–2
• Quantum rejection sampling on Bayesian networks takes O(n2^mP(e)^-1/2) time per sample, versus O(nmP(e)^-1) classically.The network structure enables efficient state preparation, and amplitude amplification supplies the speedup.Source: §I · p. 2
• The paper counts primitive circuit operations rather than oracle queries, exploiting Bayesian-network structure to efficiently construct the state-preparation circuit.The paper’s outline identifies state preparation and amplitude-amplification reflections as circuit constructions evaluated for total runtime.Source: §I · p. 2

II. BAYESIAN NETWORKS

• A Bayesian network represents a joint distribution over n bits with a directed acyclic graph and conditional probability tables for its nodes.Edges encode conditional dependencies, and a node’s table records probabilities conditioned on its parents.Source: §II · p. 2, Figure 1 · p. 3
• With maximum indegree m, the network stores at most O(n2^m) probabilities rather than O(2^n).Each node with m_i parents has a conditional-probability table of 2^m_i values.Source: §II · p. 2
• Exact inference asks for P(Q|E=e) and is #P-hard in general.The passage describes a reduction from counting satisfying assignments of an n-variable k-SAT problem.Source: §II · p. 2
• Classical sampling generates each node from the already generated values of its parents, taking O(nm) time before evidence postselection.Only samples with the specified evidence are retained, so low P(e) increases the average time per accepted sample.Source: §II · p. 2
• Quantum rejection sampling improves the P(e)^-1 factor to P(e)^-1/2 while preserving linear scaling in the number of variables.The stated scaling applies given the network structure; the excerpt does not complete the full runtime expression.Source: §II · p. 2

Definition of a qpdf

• A qpdf is required to be pure, yield samples from the full or marginal distribution when measured, and support unitary updates corresponding to every stochastic update.The section motivates q-stochasticity as useful for implementing Markov chains, Markov decision processes, and sampling algorithms on quantum states.Source: §III · p. 3

The q-sample

• The q-sample is the simplest encoding satisfying purity and q-sampling, but it fails the q-stochasticity criterion.For the single-qubit example, the required unitary is never unitary when the transition matrix is stochastic.Source: §III · p. 3

Open question

• Whether a more complicated representation can satisfy all three qpdf properties, including q-stochasticity, remains open.Adding relative phases alone does not guarantee property 3.Source: §III · p. 3

Using q-samples for inference

• Despite that failure, measuring a subset of q-sample qubits yields a marginal, and conditional gates form a q-sample for a conditional distribution.Amplitude amplification is then used to obtain the conditional sample efficiently.Source: §III · pp. 3–4

Target state

• Amplitude amplification targets the evidence-compatible component of a prepared state, with the goal of extracting the query state associated with evidence e.The target state is |Q⟩|e⟩ in the query and evidence spaces.Source: §IV · p. 4

Grover iterate

• Repeated reflections about the evidence and initial state rotate the prepared state toward the target component.The Grover iterate is expressed as a product of these two reflections.Source: §IV · p. 4

Unknown target amplitude

• When |α| is unknown, the correct number of Grover iterates can be guessed in exponential progression: apply ˆG 2k times for k = 0, 1, 2, …, and measure the evidence qubits after each attempt.Stop when the measured evidence is E = e.Source: §IV · p. 4

Algorithm

• The algorithm assumes a circuit that prepares the joint q-sample, then measures evidence qubits and, upon success, query qubits to produce the conditional sample.The query and evidence registers are placed in separate qubit groups before amplification.Source: §V · p. 4
• Starting from a q-sample of P(Q,E), amplitude amplification increases the component with evidence E=e, requiring O(P(e)^-1/2) applications of the preparation operator.The amplified query state can be measured to sample from P(Q|E=e).Source: §V · p. 4

Implementation question

• A crucial remaining question is whether the q-sample preparation operator can be implemented efficiently rather than treated as a black box.The next section addresses this implementation requirement.Source: §V · p. 4

Q-sample preparation

• For a Bayesian network with n nodes and maximum indegree m, q-sample preparation has circuit complexity O(n2^m), whereas general preparation is O(2^n).Circuit complexity counts gates after compilation into a primitive set containing CNOT and single-qubit rotations.Source: §VI · pp. 4–5

Phase flips and total complexity

• The remaining Grover-iterate phase-flip operators are also constructed, and the combined constructions make approximate inference on Bayesian networks possible with polynomial-size quantum circuits.The stated circuit-complexity measure counts primitive gates.Source: §VI · p. 5

A. Q-sample Preparation

• An arbitrary distribution over n binary variables can be prepared as a q-sample with circuit complexity O(2^n), and this bound is tight.The distribution contains 2^n − 1 arbitrary probabilities, requiring at least that many primitive operations.Source: A. Q-sample Preparation · p. 5
• Factoring P(x) into conditional probabilities lets the circuit prepare the q-sample by applying one uniformly controlled rotation for each variable.Each rotation uses earlier variables as controls and rotates the next qubit according to its conditional probability.Source: A. Q-sample Preparation · p. 5
• The construction uses Bergholm et al.’s decomposition of uniformly controlled gates into O(2^k) CNOTs and single-qubit operations.Each gate realizes a conditional probability table in the joint-distribution factorization.Source: A. Q-sample Preparation · p. 5

B. Bayesian Q-sample Preparation

• The Bayesian preparation circuit is exponentially simpler than the general q-sample preparation circuit.The indegree m depends on node ordering; finding an ordering that minimizes it is NP-hard, while natural causal ordering often comes close to optimal.Source: B. Bayesian Q-sample Preparation · p. 5
• A Bayesian q-sample for a network with n nodes and bounded indegree m can be prepared with circuit complexity O(n2^m).The construction orders nodes topologically and applies one uniformly controlled operator per node, each with at most m controls.Source: B. Bayesian Q-sample Preparation · p. 5
• Bayesian q-sample preparation forms part of the Grover iterate used for amplitude amplification.The iterate also includes reflection, or phase-flip, operators.Source: B. Bayesian Q-sample Preparation · p. 5

C. Phase Flip Operators

• The evidence phase flip can be implemented with a k-qubit controlled-Z operation and at most 2k bit flips, where k = |E|.S_0 is the special case S_e=0^n.Source: C. Phase Flip Operators · p. 5
• The controlled phase flips the phase only when all k evidence qubits are 1, with bit flips adapting it to the target evidence assignment.The complement bits are defined by ē_i ≡ 1 − e_i.Source: C. Phase Flip Operators · p. 6
• The controlled phase can use O(k) CNOTs and single-qubit operators with O(k) ancillas, or O(k²) such gates without ancillas.Figure 2 depicts the evidence-controlled bit flips and phase operation.Source: C. Phase Flip Operators · p. 6, Figure 2 · p. 6
• Table I lists circuit complexities for operators in the Grover iterate, which uses two preparation circuits and one instance of each phase-flip operator.The caption distinguishes Bayesian q-sample preparation from general q-sample preparation.Source: Table I · p. 6

D. Time Complexity

• The Grover iterate’s circuit complexity is dominated by the state-preparation operator.The phase-flip operators scale linearly with n and |E|, respectively.Source: D. Time Complexity · p. 6
• O(n2^mP(e)^−1/2) time per sample gives a square-root speedup over the classical O(nmP(e)^−1) cost.The Bayesian preparation circuit has complexity O(n2^m), and the algorithm uses O(P(e)^−1/2) applications of it.Source: D. Time Complexity · p. 6
• Quantum sampling uses O(P(e)^−1/2) applications of the Bayesian preparation operator to obtain one sample.The resulting per-sample cost is O(n2^mP(e)^−1/2).Source: D. Time Complexity · p. 6

• Bayesian-network structure enables a square-root quantum speedup in approximate inference; for general distributions, the Grover iterate would be exponential in n.Source: §VII · p. 6
• A proof-of-principle experiment could perform inference on a two-node Bayesian network using two ion-trap qubits.Source: §VII · p. 6
• The conclusion situates q-samples within an analogy between quantum states and classical probability distributions.Source: §VII · p. 6
• The inference circuit repeats until its measurement contains the evidence bits, then records the result as a sample from P(Q|E).Source: Figure 3 · p. 7
• The state-preparation operator is constructed from Theorem 2, while the phase-flip operators are constructed as shown in Fig. 2.Source: §VII · p. 7