{'fraction_non_alphanumeric': 0.043997167998381714, 'fraction_numerical': 0.027207444118539495, 'mean_word_length': 4.187565582371459, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum Factor Graphs

The natural Hilbert Space of quantum particles can implement maximum-likelihood (ML) decoding of classical information. The 'Quantum Product Algorithm' (QPA) is computed on a Factor Graph, where function nodes are unitary matrix operations followed by appropriate quantum measurement. QPA is like the Sum-Product Algorithm (SPA), but without summary, giving optimal decode with exponentially finer detail than achievable using SPA. Graph cycles have no effect on QPA performance. QPA must be repeated a number of times before successful and the ML codeword is obtained only after repeated quantum 'experiments'. ML amplification improves decoding accuracy, and Distributed QPA facilitates successful evolution.


Introduction
Recent interest in Turbo Codes [2] and Low Density Parity Check Codes [4,6] has fuelled development of Factor Graphs and associated Sum-Product Algorithm [5,1] (SPA), with applications to error-correction, signal processing, statistics, neural networks, and system theory. Meanwhile the possibility of Quantum Computing has sparked much interest [9,10], and Quantum Bayesian Nets have been proposed to help analyse and design Quantum Computers [12,11]. This paper links these areas of research, showing that quantum resources can achieve maximum-likelihood (ML) decoding of classical information.
The natural Hilbert Space of a quantum particle encodes a probability vector, and the joint-state of quantum particles realises the 'products' associated with SPA. SPA summary is omitted as quantum bits (qubits) naturally encode the total joint-probability state. Dependencies between vector indices become 'entanglement' in quantum space, with the Factor Graph defining dependency (entanglement) between qubits. Graph function nodes are implemented as unitary matrix 2 -vector products followed by quantum measurement. This is the Quantum Product Algorithm (QPA). As QPA avoids summary it avoids problems encountered by SPA on graphs with short cycles. Moreover, whereas SPA is iterative, using message-passing and activating each node more than once, QPA does not iterate but must successfully activate each node only once. However the (severe) drawbacks with QPA are as follows: 1) Each function node must be repeatedly activated until it successfully 'prepares' it's local variable nodes (qubits) in the correct entangled state -any activation failure destroys evolution in all variable nodes already entangled with local variables. 2) Once a complete Factor Graph has successfully evolved, final quantum measurement only delivers the ML codeword with a certain (largest) probability. Repeated successful evolutions then determine the ML codeword to within any degree of confidence. This second drawback can be overcome by suitable "ML Amplification" of QPA output, prior to measurement. 2 'Unitary' means that U satisfies UU † = I, where † means 'conjugate transpose'. Section 2 presents QPA, highlighting its ability to deliver the optimal output joint-state, unlike SPA. Quantum systems describe the exact joint-state by appropriate 'entanglement' with and measurement of ancillary qubits. Section 3 considers a simple example of QPA on Quantum Factor Graphs, showing that iteration on graphs with cycles is unnecessary because QPA avoids premature summary. Section 4 shows how to amplify the likelihood of measuring the ML codeword from QPA output. Unfortunately QPA must be repeated many times and/or executed in parallel to have a hope of successful completion. Suitable distributed QPA scheduling is discussed in Section 5, and it is argued that successful QPA completion is conceivable using asynchronous distributed processing on many-node Factor Graphs. This paper does not deal with phase properties of quantum computers. It is expected that the inclusion of phase and non-diagonal unitary matrices will greatly increase functionality of the Quantum Factor Graph.
The aim of this paper is not to propose an immediately realisable implementation of a quantum computer. Rather, it is to highlight similarities between graphs for classical message-passing, and graphs that 'factor' quantum computation. The paper also highlights the differences between the two graphs: whereas classical graphs can only ever compute over a tensor product space, the quantum graph can compute over the complete entangled (tensor-irreducible) space.
U fg is unitary, and the U f of Fig 1 and subsequent figures always implies the action of U fg together with the measurement of an ancillary qubit, z, as described below. A qubit, x i , can be in states 0 or 1 or in a statistical superposition of 0 and 1. Let qubits x 0 , x 1 be initialised (by the black boxes) to states x 0 = (α 0 , β 0 ) T and x 1 = (α 1 , β 1 ) T , where α i , β i are complex probabilities such that |α i | 2 + |β i | 2 = 1. For instance, x 0 is in states 0 and 1 with probabilities |α 0 | 2 and |β 0 | 2 , respectively. Let an ancillary qubit, z, be initialised to state 0, i.e. z = (1, 0). Then the initial joint probability product-state of qubits |s 0 | 2 + |s 1 | 2 + |s 2 | 2 + |s 3 | 2 = 1, and '⊗' is the tensor product. The element at vector index v is the probability that the qubits are in state v. For instance, qubits x 0 x 1 z are in joint-state 010 with probability |s 2 | 2 . Subsequent measurement of a subset of the qubits projects the measured qubits to a fixed substate with a certain probability, and 'summarises' the vector for the remaining nonmeasured qubits. Thus QPA is as follows, we collapse z to 0, and x 0 , With probability p g = |s 0 g 0 | 2 + |s 1 g 1 | 2 + |s 2 g 2 | 2 + |s 3 g 3 | 2 we collapse z to 1, and x 0 , x 1 to joint-state S g = µ 1 (s 0 g 0 , s 1 g 1 , s 2 g 2 , s 3 g 3 ) T . µ 0 and µ 1 are normalisation constants. p f + p g = 1. S f is our desired QPA result.
Successful QPA completion is self-verified when we measure z = 0.
In contrast, classical SPA computes S f = U f A (with probability 1) and must then perform a subsequent 'summary' step on S f before returning a result for each variable separately. This result is, For instance, for x 0 = 0 we sum the two classical 3 probabilities of S f where x 0 = 0 to get |s 0 f 0 | 2 + |s 2 f 2 | 2 . Similarly, for x 0 = 1 we summarise to |s 1 f 1 | 2 + |s 3 f 3 | 2 . It is in this sense that SPA is a 'tensor-approximation' of QPA.
We identify the following successively accurate computational scenarios (decoding modes) for a space of N binary-state variables: • Hard-Decision operates on a probability space, • Soft-Decision operates on a probability space, • Quantum Soft-Decision operates on a probability space, . C has distance 2, which is optimal for length 2 binary codes: in general if U f cannot be tensor-decomposed then it represents a code C with good distance properties. Initially, let Then A = ( √ .24, 0.6, 0.4, √ 0.24, 0, 0, 0, 0) T , and S f = 1 √ 2 (1, 0, 0, 1) T . p f = 0.48, so, on average, 48 S f outputs are computed for every 100 QPA attempts. The ML codeword is both 00 and 11, and when S f is measured, 00 and 11 are equally likely to be returned. In contrast, classical SPA for the same input returns x 0 = x 1 = ( 1 2 , 1 2 ), implying (wrongly) an equally likely decode to any of the words 00, 01, 10, 11. So even in this simplest example the advantage of QPA over SPA is evident. complexity. Consequently only limited variable 'clustering' is desirable, although too little clustering 'thins out' the solution space to an insufficient highly-factored product space. This is the fundamental Factor Graph tradeoff -good Factor Graphs achieve efficient SPA by careful variable 'separation', ensuring the joint product space is close enough to the exact (non-summarised) non-product space.

Entangled Space for QPA
In contrast, although x 0 and x 1 are physically separated in Fig 1, quantum nonlocality must take into account correlations between x 0 and x 1 . Their joint-state now occurs over the union of product and (much larger) non-product (entangled) space (Entangled-Decision mode). An entangled joint-state vector cannot be tensor-factorised over constituent qubits. QPA does not usually output to product space because the joint-state of output qubits is usually entangled. In fact QPA is algorithmically simpler than SPA, as SPA is a subsequent tensor approximation of QPA output at each local function.

Example
Let the diagonal of U f be (1, 0, 0, 1). Initialise x 0 and x 1 to joint-product- A final measurement of qubits x 0 and x 1 yields codewords 11 and 00 with probability 2 3 , and 1 3 , respectively. In contrast SPA summarises S f to . Although a final 'hard-decision' on x 0 and x 1 chooses, correctly, the ML codeword x 0 = x 1 = 1, the joint-product-state output, 1 (1, 2, 2, 4) T assigns, incorrectly, a non-zero probability to words 01 and 10.

A Priori Initialisation
To initialise x 0 to (α 0 , β 0 ) T , we again use QPA. Let the diagonal of U f (for the left-hand black box of Fig 1) be (α 0 , β 0 ). Then the diagonal of U g is ±i( and this occurs with probability p f = 0.5. x 1 is initialised likewise.

Comments
The major drawback of QPA is the significant probability of QPA failure, occurring when z is measured as 1. This problem is amplified for larger Quantum Factor Graphs where a different z is measured at each local function; QPA evolution failure at a function node not only destroys the states of variables connected with that function, but also destroys all states of variables entangled with those variables. QPA is more likely to succeed when input variable probabilities are already skewed somewhat towards a valid codeword. Section 3 shows how QPA can operate successfully even when SPA fails.

Quantum Product Algorithm on Factor Graphs with Cycles
This section shows that graph cycles do not compromise QPA performance.
Consider the Factor Graph of  Initialise as follows (using classical probabilities), Hard-decision gives x 0 x 1 x 2 x 3 = 1000, which can then be decoded algebraically to codeword 0000. However optimal soft-decision would decode to either x 3 x 2 x 1 x 0 = 1011 or 1101, with equal probability. Because of the small graph cycle SPA fails to decode correctly, and settles to the joint-product-state, A final hard-decision on this output gives non-codeword x 0 x 1 x 2 x 3 = 1000 which can then be decoded algebraically, again to codeword 0000. In contrast, successful QPA outputs the optimal entangled joint-state,  successful QPA computes the optimal non-product joint-state,  . Numerous executions of QPA on the same input will verify that 11 is, indeed, the ML codeword. However these numerous executions must output to a length 2 N final averaging probability vector (for N qubits). We do not want to store such an exponential vector. Instead, therefore, we 'amplify' the statistical advantage of 11 over 00 prior to measurement, thereby making 11 significantly more likely to be read. This is achieved by computing the square of each quantum vector element as follows. Consider two independent QPA executions on the same input, both outputting S f . Associate these outputs with qubits x 0,0 , x 1,0 , and x 0,1 , x 1,1 . The joint-state of qubits x 0,0 , x 1,0 , x 0,1 , x 1,1 is,

Consider the unitary permutation matrix
Only the '1' positions in the first four rows are important. Performing P on x 0,0 , x 1,0 , x 0,1 , x 1,1 , gives, We then measure qubits x 0,1 , x 1,1 . With probability p a 0 = 5 9 we read x 0,1 = We can perform QPA on large Factor Graphs, then amplify the result k times to ensure a high likelihood of measuring the ML codeword, as described above.
However the above amplification acts on the complete graph with one operation, P. It would be preferable to decompose P into 4×4 unitary matrices which only act on independent qubit pairs x i,0 and x i,1 , thereby localising amplification. With probability p a 0 = 5 9 we read x 0,1 = 0, in which case x 0,0 is forced into joint state s f,1 = 1 √ 5 (1, 2), which is the element-square of s f . Due to the exact form of our joint-state vector, S f , this single measurement is enough to also force x 0,0 x 1,0 into joint state S f,1 . However, for a general function S f , we should perform Q on every qubit pair, x i,0 x i,1 , then measure x i,1 ∀i. This is equivalent to performing P ′ = Q ⊗ Q on (re-ordered) joint-state vector x 0,0 x 0,1 x 1,0 x 1,1 , and this is identical to performing P on x 0,0 x 1,0 x 0,1 x 1,1 . The probability of measuring x 1,0 = x 1,1 = 0 is the same whether P or Q is used. The same process is followed to achieve element 2 k th powers.

The Price of Amplification
There is a statistical cost to qubit amplification. Let s = (α, β) T be the initial state of a qubit x, where, for notational convenience, we assume that α and β are both real. Then α 2 +β 2 = 1 and, given 2 k qubits all identically prepared in state s, the likelihood of preparing one qubit in (unnormalised) state s k = (α 2 k , β 2 k ) T is γ k , where, and r k = α 2 k + β 2 k . For a qubit in state s k , the probability of selecting the ML codebit is, (assuming α ≥ β). We can plot γ k against P M k for various α 2 as k varies, as shown in   as failure occurs when a local ancillary qubit, z, is measured as 1, or when a local amplifying qubit is measured as 1. Therefore node localities with high likelihood of successful evolution (i.e. with positively skewed input probabilities) are likely to evolve first. These will then encourage other self-contradictory node localities to evolve successfully. In contrast, non-distributed QPA on large Factor Graphs using one large global function is very unlikely to ever succeed, especially for graphs encoding low-rate codes.
Therefore the probability of successful completion of both U f01 and U f23 after exactly q parallel attempts (no less) is, Given successful completion of U f01 and U f23 , the probability of subsequent successful completion of U f12 is, Therefore the probability of successful completion of U f01 and U f23 , immediately followed by successful completion of U f12 is, p 0→3 (q) = p 0−3 (q − 1)p ′ f 12 , and the probability of successful completion of U f01 and U f23 , immediately followed by completion failure of U f12 is, p 0→3 (q) = p 0−3 (q − 1)(1 − p ′ f 12 ). Therefore the probability of successful completion after exactly t steps of U f01 and U f23 in parallel, followed by U f12 , is, where D(k) is the set of unordered partitions of k. Therefore the probability of successful completion after at most t steps of U f01 and U f23 in parallel, followed by U f12 , is, In contrast, for non-distributed QPA, the probability of successful completion, after at most t steps, of U, (the bottom graph of Fig 5) is . Figs 6 and 7 show plots of p m (t) and P (t) versus t for α 0 = α 1 = α 2 = α 3 = w as w varies, and α 0 = u, α 1 = α 2 = α 3 = w = 0.9 as u varies, respectively. For Fig 7, low values of u indicate a contradiction between x 0 and the other three variables. In particular the contradiction is so pronounced when α 0 = 0.0 that successful QPA completion is highly unlikely.
More generally, this indicates that severe internal Factor Graph contradictions are fatal to QPA (as they are for SPA). Both Fig 6 and 7 indicate that, due to initial latency of distributed processing, non-distributed QPA appears marginally faster for the first few steps. However, after a few steps distributed QPA in general becomes marginally faster. In fact results are unfairly biased towards the non-distributed case, as it is assumed that attempts to complete U and U fij have the same space-time-complexity cost, whereas U is far more costly. Hence, even for this smallest example, Distributed QPA outperforms non-Distributed QPA.   0, 0, 1, 0, 1, 1, 0). We allow U f012 , U f345 , and U f678 to operate independently and in parallel. If U f012 fails to establish, then it does not destroy any successful evolution of U f345 or U f678 , as the three localities are not currently entangled. Once U f012 , U f345 , and U f678 have completed successfully, the probability of successful subsequent completion of U f258 is, in general, ampli- for notational convenience, we assume all values are real. Then α 2 i + β 2 i = 1, ∀i. Let the probability of successful completion after at most t steps of U f012 , U f345 , and U f678 in parallel, followed by U f258 , be p m (t), and the probability of successful completion, after at most t steps, of a non-distributed version of    that two local variables can be strongly or weakly entangled by identifying the mutual square function nodes with strongly or weakly-entangling matrices, respectively. In particular, two neighbouring nodes may be 'locally disconnected' by setting the function node joining them to a tensor-decomposable matrix, (i.e. zero-entangling). The quantum computer is then measurement-driven.
The concept of measurement-driven quantum computation has also recently been pursued in [8], where a uniform entanglement is set-up throughout the array 7 prior to computation via measurement.  should be generalised to cope with phase shift in order to decode quantum information. This is the subject of ongoing research.

Conclusion and Discussion
The Quantum Product Algorithm (QPA) on a Factor Graph has been presented for Maximum-Likelihood (ML) Decoding of Classical 'soft' information using quantum resources. The relationship of QPA to the Sum-Product Algorithm (SPA) has been indicated, where avoidance of summary allows QPA Figure 13: Free-Running Distributed QPA with one 'Bad' Variable to overcome small graph cycles. Quantum Factor Graphs use small unitary matrices which each act on only a few qubits. QPA is measurement-driven and is only statistically likely to succeed after many attempts. The ML codeword is obtained with maximum likelihood by measuring the entangled vector resulting from successful QPA. To ensure a high probability of measuring the ML codeword QPA output can be amplified prior to measurement. The complete ML decoder is only successful after many attempts. Finally, free-running Distributed QPA is proposed to improve the likelihood of successful QPA completion. The free-running distributed structure suggests further benefit will be obtained by introducing Fault-Tolerance in the form of redundant function and variable nodes. Phase aspects of QPA have yet to be explored. This paper has been written to demonstrate the exponential capacity of quantum systems, and their natural suitability for graph decompositions such as the Factor Graph.
The paper has not tried to deal with quantum noise and quantum decoherence, but one can expect the Factor Graph form to 'gracefully' expand to cope with the extra redundancy necessary to protect qubits from decoherence and noise.
When viewed in the context of entangled space, it is surprising how successful classical message-passing algorithms are, even though they are restricted to operate in tensor product space. This suggests that methods to improve the Therefore the probability of successful completion of U f012 , U f345 , and U f678 , immediately followed by successful completion of U f258 is, p 0→8 (q) = p 0−3−6 (q− 1)p ′ f 258 , and the probability of successful completion of U f012 , U f345 , and U f678 , immediately followed by completion failure of U f258 is, p 0→8 (q) = p 0−3−6 (q − 1)(1 − p ′ f 258 ). The probability of successful completion after exactly t steps of U f012 , U f345 , and U f678 in parallel, followed by U f258 , is, where D(k) is the set of unordered partitions of k. Therefore the probability of successful completion after at most t steps of U f012 , U f345 , and U f678 in parallel, followed by U f258 , is, In contrast, the probability of successful completion, after at most t steps, of a non-distributed version of