extfieldsofstudy:
Computer Science
Physics

s2fieldsofstudy:
Computer Science
Physics

text:
What limits the simulation of quantum computers?

It is well established that simulating a perfect quantum computer with a classical computer requires computing resources that scale exponentially with the number of qubits $N$ or the depth $D$ of the circuit. Conversely, a perfect quantum computer could potentially provide an exponential speed up with respect to classical hardware. Real quantum computers however are not perfect: they are characterized by a small error rate $\epsilon$ per operation, so that the fidelity of the many-qubit quantum state decays exponentially as $ {\cal{F}} \sim (1-\epsilon)^{ND}$. Here, we discuss a set of classical algorithms based on matrix product states (MPS) which closely mimic the behavior of actual quantum computers. These algorithms require resources that scale linearly in $N$ and $D$ at the cost of making a small error $\epsilon$ per two-qubit gate. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that $\epsilon$ can be decreased at a polynomial cost in computing power down to a minimum error $\epsilon_\infty$. Getting below $\epsilon_\infty$ requires computing resources that increase exponentially with $\epsilon_\infty/\epsilon$. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates of depth $D=20$, a fidelity ${\cal F}\ge 0.002$ can be reached on a single core computer in a few hours. It is remarkable that such a high fidelity can be obtained using a variational ansatz that only spans a tiny fraction $(\sim 10^{-8})$ of the full Hilbert space. Our results show how the actual computing power harvested by noisy quantum computers is controlled by the error rate $\epsilon$.

It is well established that simulating a perfect quantum computer with a classical computer requires computing resources that scale exponentially with the number of qubits N or the depth D of the circuit. Conversely, a perfect quantum computer could potentially provide an exponential speed up with respect to classical hardware. Real quantum computers however are not perfect: they are characterized by a small error rate per operation, so that the fidelity of the many-qubit quantum state decays exponentially as F ∼ (1 − ) N D . Here, we discuss a set of classical algorithms based on matrix product states (MPS) which closely mimic the behavior of actual quantum computers. These algorithms require resources that scale linearly in N and D at the cost of making a small error per two-qubit gate. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that can be decreased at a polynomial cost in computing power down to a minimum error ∞. Getting below ∞ requires computing resources that increase exponentially with ∞/ . For a two dimensional array of N = 54 qubits and a circuit with Control-Z gates of depth D = 20, a fidelity F ≥ 0.002 can be reached on a single core computer in a few hours. It is remarkable that such a high fidelity can be obtained using a variational ansatz that only spans a tiny fraction (∼ 10 −8 ) of the full Hilbert space. Our results show how the actual computing power harvested by noisy quantum computers is controlled by the error rate .

I. INTRODUCTION
Operating a quantum computer is a race against the clock. The same phenomena enabling the potential computing power of quantum computers-entanglementis also responsible for decoherence when it occurs with unmonitored degrees of freedom. The main challenge of quantum computing is to quickly build entanglement between the qubits before imperfections or decoherence overly corrupt the quantum state.
As different experimental platforms for quantum manipulation make rapid and impressive advances, there has been a justifiable interest in the computational capability of near-term quantum computers [1]. One of the key questions is when and how to achieve the goal of "quantum supremacy" [2], which is the crossover point where a quantum system ceases to be within reach of simulation on a classical computer. Precise circuits and fidelity metrics have been designed to meet this goal [3]. Recently, an experiment using 53 qubits and a circuit of depth D = 20 has reached a multi-qubit fidelity F = 0.002 [4]. According to the authors, such an experiment would take thousands of years to be simulated on the largest existing supercomputer. This statement was then challenged by another estimate which claims that only two days would be needed [5]. Such a disparity between estimates raises the question of the difficulty of simulating a quantum computer and consequently of the true computing power realized in a quantum computer.
The implicit assumption behind quantum supremacy as well as the most appealing applications of quantum computing is that a quantum computer is exponentially hard to simulate. Indeed, in recent years many tech-niques have been developed to simulate quantum computers, and they all have an exponential cost in some parameter. A brute force approach where one holds the full quantum state in memory as a large vector of size 2 N (N : number of qubits) requires a computing time and memory that scales exponentially with N but linearly with the depth D of the circuit. Other approaches require a computing time that scale exponentially with the number of two-qubit gates [6][7][8][9], with the number of non-Clifford gates [10] and/or with the number of gates that are non-diagonal in a chosen basis [11,12]. In all cases, the required computing resources are exponential so that getting beyond N = 50 and a depth D = 20 for an arbitrary circuit is extremely difficult.
In this article, we discuss a class of algorithms where the limiting factor is the fidelity with which the calculation is performed while the computing time is linear in both the number of qubits N and the depth D. These algorithms "mimic" actual quantum computers in the sense that the difficulty lies in increasing the fidelity of the calculation: a small finite error is made each time a twoqubit gate is applied to the state. Therefore, they offer a better reference point to assess the computing power harvested by actual quantum chips.
Our algorithms are based on tensor networks and more precisely on matrix product states (MPS) [13]. MPS have been recognized very early as an interesting parameterization of many-qubit quantum states for quantum simulations [6] and its generalizations are used in some of the most advanced simulation tools [14]. So far, the focus of classical simulations of quantum hardware has been to build essentially exact simulations techniques and little attention has been devoted to approximate techniques. Interestingly these exact techniques can require one to go well beyond double precision calculations [15]. However, the historical success of MPS has not been for exact calculations but for the development of controlled approximate techniques to address quantum many-body physics problems. This includes the celebrated density matrix renormalization group (DMRG) algorithm [16] which has provided precise solutions to a number of one dimensional and quasi-one-dimensional problems, as well as time-dependent extensions [17] and generalizations to higher dimensions through the projected entangled pair states (PEPS) [18] or the multi-scale entanglement renormalization ansatz (MERA) [19] tensor network formats. At the root of these successes is the fact that MPS naturally organizes states according to the amount of entanglement entropy between different parts of the system. Hence, slightly entangled systems can be easily represented with MPS. As entanglement entropy grows, one eventually truncates the basis. The associated error can be made arbitrarily small by keeping a larger basis. In this article, we construct such an approximate technique in the context of quantum computing. Our chief result is that fidelities comparable to those reached experimentally require parameterizations spanning only a tiny fraction of the total Hilbert space.

II. POSSIBLE STRATEGIES FOR APPROXIMATE SIMULATIONS OF QUANTUM CIRCUITS
Let us start by discussing possible strategies for simulating quantum circuits in an approximate manner. Suppose that we have split the qubits into two different sets A and B with respectively N A and N B qubits (N A + N B = N ). Let us consider the two-qubit gates that connect A and B and ignore gates internal to A or B. Performing a singular value decomposition (SVD) of such a gate, it can be written as a sum of terms that act separately on A and B. This sum contains two terms for the case of usual gates (Control-NOT and Control-Z) and at most four terms for an arbitrary two-qubit gate. It follows that computing the state after n of these gates amount to keeping track of 2 n (up to 4 n ) different amplitudes. These amplitudes are the discrete analogue of the Feynman paths and are referred as such in the literature. For the random circuits that will be considered in this article, these 2 n amplitudes have essentially random phases. It follows that if one keep track of just a single path, one reaches an overall multi-qubit fidelity F = (1/2) n (or F = (1/4) n in the worst situation). This very simple strategy could be used to simulate an arbitrary large number of qubits with low fidelity per gate in a computing time ∼ n. However, if one wants to keep a fixed fidelity per gate f defined as F = f n , in analogy with real quantum computers, the number of paths N path that must be tracked during the simulation is N path = (2f ) n , hence increases exponentially with n. Such a strategy has been used in [4] to validate the experimental results.
We now seek algorithms where a constant fidelity f can be obtained at a constant computing cost per gate, independently of the total number of gates n. One starts by writing a general state for the bipartite system as, where the states |a (|b ) form an orthonormal basis of A (B). Performing a singular value decomposition (SVD) we can define an orthonormal basis (with similar notation for the B subsystem) and arrive at the usual Schmidt decomposition of |Ψ : in terms of a finite number of singular values S µ . States with only one non-zero singular value S 0 = 1 are simple product states. A measure of the number of singular values needed to describe the state is given by the entanglement entropy is the reduced density matrix for the subsystem A (B). The general strategy of DMRG-like algorithms is to keep only a finite number χ of singular values. After a two-qubit gate that connects A and B, one performs a SVD decomposition of Ψ ab and truncate the state by keeping only the χ largest singular values. When χ e S this procedure is essentially exact. As the entanglement increases, this procedure lead to a certain fidelity per gate f < 1 that can be controlled by increasing the parameter χ. Of interest to the present article is the typical value of f that can be reached in a reasonable computing time.

A. MPS representation of the state
We first consider a one dimensional network of N qubits where two-qubit gates can be only applied directly between nearest neighbors. Within this connectivity, gates acting on other non-neighboring qubits are still possible at the cost of using ∼ N SWAP operations to bring the qubits onto neighboring sites. We define our MPS state in terms of N tensors M (n) as where the "physical" indices i n ∈ {0, 1} span the 2 N dimensional Hilbert space while the bond (or virtual) indices µ n ∈ {1, ..., χ n } control the maximum degree of entanglement allowed by the MPS. |x is a shorthand for |i 1 i 2 ...i N . A sketch of the MPS structure is shown in Fig. 1b. We enforce χ n ≤ χ so that the parameter χ controls the error rate made by our algorithm as well as the computational cost for running it. Its memory footprint is N χ 2 while applying a two-qubit gate takes ∼ χ 3 operations. To be acceptable, our algorithm must provide the same features that a real quantum computer would provide. Applying a one-qubit gate U on qubit n can be done exactly and without increasing any of the χ n : it simply amounts to updating the corresponding tensor M (n) → M (n): as shown in Fig. 2(a). Calculating the overlap between different MPS states or calculating individual wavefunction amplitudes i 1 i 2 ...i N −1 i N |Ψ can be done with contraction algorithms which, for MPS, can be done exactly in ∼ N χ 3 operations (see e.g. [13] for a detailed description of standard MPS algorithms). It follows that one can also sample from the distribution | i 1 i 2 ...i N −1 i N |Ψ | 2 within the same complexity. Quantum measurements (sampling of a given qubit followed by its projection) can also be done efficiently in a straightforward manner [20].
To perform a two-qubit gate U between qubit n and qubit n + 1, one first transforms the MPS into the socalled "canonical form" centered around the qubits of (a) Applying a single qubit gate to an MPS can be done without approximation by multiplying the gate by a single MPS tensor. (b) To apply a two-qubit gate to qubits n and n + 1, one contracts the corresponding tensors together, then applies the gate. To restore the MPS form, the resulting tensor is decomposed with an SVD truncated to keep the largest χ singular values, and the matrix of singular values is multiplied into one of the unitary factors X or Y .
interest, through a series of QR factorizations [13]. This step is crucial for the accuracy of truncations of the MPS. The steps to apply the gate are then shown in Fig. 2(b). One first forms the two-qubit tensor Then one applies the two-qubit gate U and obtains In a last stage, considering the tensor T as a matrix with indices spanned by (i n , µ n−1 ) and (i n+1 , µ n+1 ), one performs a singular value decomposition and writes where the tensors X and Y are formed of orthogonal vectors while the vector S µ contains the singular values of T . Here S µ has up to 2χ components (irrespectively of the nature of the two-qubit gate) so that exact algorithms imply a doubling of χ after each application of a twoqubit gate. In the spirit of DMRG like algorithms, we truncate S µ and keep only its χ largest components to obtain S µ . The new MPS tensors are then simply given by which completes the algorithm. Overall, the cost of applying a two-qubit gate is dominated by the SVD step which scales as χ 3 . We emphasize that such an algorithm can do anything that a quantum computer does but the reverse statement is not true: in the MPS approach, one holds the full wavefunction in memory which provides much more information than can be obtained from samples of the wavefunction. For instance, one can compute bipartite entanglement entropy of an MPS, and it is straightforward to calculate quantities such as observables or correlation functions without any statistical errors. The MPS format also satisfies the sample and query access criteria needed for quantum inspired de-quantizing algorithms [21].

B. Random Quantum Circuit
Fig . 1a shows the quantum circuit used in our numerical experiments. It consists of alternating layers of onequbit and two-qubit gates. This circuit has been designed following the proposal of [3] in order to create strongly entangled states in as few operations as possible. It it believed to be one of the most difficult circuit to simulate on a classical computer since its many-qubit quantum state is extremely sensitive to modification of any of the gates. The one-qubit gates U n represented as colored squares in Fig. 1a are chosen randomly such as to remove any structure or symmetry from the many qubit state. A gate U n is a rotation U n = exp(−iθ n σ. m n ) of angle θ n around a unit vector m n = (sin α n cos φ n , sin α n sin φ n , cos α n ) ( σ is the vector of Pauli matrices). We take the angles θ n , α n , and φ n to be uniformly distributed (note that the resulting matrix U n is not distributed according to the Haar distribution of U (2)). While the U n are random, the actual sequence used is carefully recorded for comparison with e.g. exact calculations. We call the number of two-qubit gate layers applied the depth D of the circuit, focusing on the number of two-qubit gate layers because those are the only source of imperfection in our calculations. In real quantum computers, twoqubit gates also dominate the errors over one-qubit gates in terms of fidelity. However real quantum computers also have other sources of error (decoherence, unknown couplings between qubits, leakage to non-computational states...) not present in the algorithm. After a depth D ∼ N , the state obtained with the circuit of Fig. 1a is totally scrambled and well described by a Porter-Thomas distribution. This is illustrated in Fig. 3 where the cumulative distribution of p x = | x|Ψ | 2 is compared to the Porter-Thomas form for various maximum MPS bond dimensions (main panel) and for various depths using exact calculations (inset). One indeed observes that the dis- tribution quickly approaches the chaotic Porter-Thomas distribution as one increases the bond dimension χ.

C. Effective two-qubit gate fidelity
Let us introduce the main quantity of interest for this study, the effective two-qubit fidelity f n . The effective two-qubit fidelity f n is the computational analogue to the fidelity reported experimentally for two-qubit gates. f n = 1 for a perfect calculation, but the truncation of the MPS will induce 0 < f n < 1.
Let us call |Ψ T (n) the MPS state after a sequence of n individual two-qubit gates (n ≈ (N − 1)D/2 for the circuit of Fig. 1a). Up to irrelevant one-qubit gates, |Ψ T (n) is obtained by applying one Control-Z gate C Z onto |Ψ T (n − 1) followed by the truncation operation which introduces a finite error. We define the effective fidelity f n as, and the corresponding error rate n as, f n can be calculated using the contraction algorithm in N χ 3 operations. However, when the MPS is in canonical form, f n is simply obtained without any additional calculations as, We have explicitly checked the equivalence between the two algorithms. A typical simulation is shown in Fig. 4 for the circuit with the Control-Z gate. At small depth D < 2 log 2 χ, the simulation is exact and f n = 1. Above this threshold, one starts to truncate the MPS after each two-qubit gate. We observe a transient regime where f n decreases after which f n quickly saturates at a constant value, here around 0.988. The first thing to notice in Fig. 4 is that these simulations are many orders of magnitude easier than an equivalent perfect calculation: simulating the exact state for N = 60 and D = 200 would be out of reach even with thousand of years of computing time on the largest existing supercomputer. Yet here, these simulations of a noisy quantum computer have been performed on a laptop. The averaged fidelity for a modest χ = 64 is better than 99% which already corresponds to qubits of very good quality. This is rather remarkable since the percentage of the Hilbert space spanned by the MPS ansatz is only a very tiny fraction ∼ 10 −13 percent of the whole Hilbert space. After the transient regime, f n is, up to some fluctuations, independent of both D and N . The second statement is true up to small 1/N corrections. These corrections arise from the fact that the fidelity associated with gates applied on the edge of the system (i.e. associated to matrices M (i) with i < 2 log 2 χ or N − i < 2 log 2 χ) is always equal to unity since the en-tanglement entropy associated to the subsystem of qubits i < a is bounded by S ≤ a log 2.
Our main goal is to understand how the residual error n = 1 − f n decreases as one increases the bond dimension χ. As χ approaches χ ∼ 2 N/2 , one must have n → 0. However, here we are interested in the regime χ 2 N/2 which remains accessible to simulations. Fig. 5 shows how the residual error n = 1 − f n decreases with increasing the bond dimension. The main finding of Fig. 5 is that the residual error per gate at large depth D and number of particle N eventually saturates at a finite value, in this case around ∞ ≈ 6 × 10 −3 . In other words, this algorithm can simulate any 1D quantum computer that has a two-qubit gate fidelity smaller than f ∞ = 99.4% at a linear cost in both N and D . As the depth or number of qubits is reduced, the average fidelity increases. The black cross in Fig. 5 corresponds to a calculation where only the last part of the circuit has been taken into account in the calculation of the average fidelity, i.e. the average is performed for D > 50 where the system has already entered its stationary regime. As we shall see, decreasing the error rate beyond ∞ requires an exponential effort.

IV. LINKS BETWEEN TWO-QUBIT AND MULTI-QUBIT FIDELITY
Before investigating the origin of ∞ , we make a short detour to discuss how the effective two-qubit fidelity f n is related to the actual N-qubit fidelity F of the state and is related to practical estimates of the fidelity that can be measured experimentally.

A. Multi-qubit fidelity
Let us call |Ψ P (n) the exact perfect state after n two-qubit gates-meaning it is never truncated or otherwise approximated at any stage of its evolution by the circuit-while |Ψ T (n) is the truncated MPS state (P stands for Perfect and T for Truncated). The N-qubit fidelity F is defined as, The fidelity F is a direct measure of how reliable is our truncated state. As the errors accumulate, it is natural to expect that the fidelities f n are multiplicative, Eq. (17) is indeed a very accurate approximation. An analytical argument will be given below. The validity of Eq. (17) can also been shown by numerical simulations. Fig. 6 shows the fidelity versus D for N = 20 particles obtained in two independent ways. The symbols corresponds to a direct calculation of F while the lines correspond to the the right hand side of Eq. (17). We find an almost perfect match in all the regimes that we have studied. Eq. (17) is a very useful result: it relates a property of the perfect state (left hand side) to a property solely defined in terms of the MPS (right hand side). It allows us to easily estimate the fidelity in regimes where we do not have access to the exact state anymore. When f n has reached its stationary value f ∞ , Eq. (17) simplifies into In an actual experiment, one cannot measure the f n but rather one has access to an estimate of F(n) (see the subsection below). To compare the accuracy of the simulations with the capabilities of actual quantum chips, we therefore define the average two-qubit fidelity f av after n two-qubit gates, where the second equality is specific to the quantum circuit studied here. Derivation of Eq. (17). Let us define a full basis of orthogonal states |α such that state |1 ≡ |Ψ T (n − 1) is our truncated state and we complement state |1 with an arbitrary basis. Writing |Ψ P (n − 1) in that basis as |Ψ P (n − 1) = 2 N α=1 p α |α , we have p 1 = F(n − 1). Similarly, we write |Ψ T (n) = √ f n . From these definitions, the fact that C Z is unitary and that |Ψ P (n) = C Z |Ψ P (n − 1) , we have, As the fidelity goes down, the p α and t α become increasingly decorrelated, in particular in sign. Assuming random signs between the p α and the t α and using that p α ∼ 1/ √ 2 N , we find that the second term in the above equation is at most of order 1/ √ 2 N and is therefore negligible. Eq. (17) follows directly.
We end this subsection by proving a weaker but exact statement valid for any circuit. Schwartz inequality implies that, from which we obtain, The Eq. (22) bound is exact, but saturating this bound in practice implies that all the terms p α t α interfere constructively which is not realized in actual circuits. Eq. (22) implies that from which one can prove that, The exact statement Eq. (24) can be useful for small depth circuits where the actual decrease of the fidelity F(n) is indeed linear with n, before one enters into the true exponential regime.

B. Other fidelity metrics
So far we have used the overlap F between the exact state |Ψ P and our approximate state |Ψ T as our metric for the fidelity of the calculation. It is a natural metric as it measures the probability for the approximate state to be in the exact state one. It is bounded 0 ≤ F ≤ 1 and is nicely related to the probabilities per gate f n through the formulas of the preceding subsection.
However F cannot be directly measured experimentally, so that other fidelity metrics must be designed. Indeed, in an actual quantum computer, the only existing output are samples of bitstrings x = i 1 i 2 ...i N distributed according to | x|Ψ T | 2 . A natural metric is the cross entropy defined as Cross entropy is a standard tool of machine learning and has several interesting properties. First it is measurable through sampling as where the x m are the output of the quantum computer when the experiment is repeated M times. Second, the cross entropy between two distributions | x|Ψ T | 2 and | x|Ψ P | 2 is maximum when the two distribution are identical. Hence it is a genuine measure of the likelihood of the two distributions. Cross entropy was proposed in [3] as a fidelity metric. Note however that the cross entropy is not a symmetric function of the two distributions. In particular it is strongly affected by particular configurations x where | x|Ψ P | 2 is very low but | x|Ψ T | 2 is not. Cross entropy was eventually abandoned by the Google team and replaced [4] by the cross entropy benchmarking (XEB) defined as XEB is also sampleable and is symmetric with respect to the two distributions. When the approximate state is the uniform distribution, the XEB metric vanishes, B = 0 indicating a total lack of fidelity. However, when the approximate state is actually exact, the value of the XEB metric can be arbitrary. When the approximate state is exact and distributed according to the Porter Thomas distribution (which happens in our circuits after a few cycles), then the XEB metric gets a well defined B = 1 0 10 20 30 40 50 D value. The XEB metric is not in general a good measure of the likelihood between two distributions: for a given perfect state, it is maximum when the approximate state is sharply peaked around the values of x where the perfect state is maximum. In our circuit the initial value of XEB is exponentially high B = 2 N − 1 and quickly decreases as the distribution approaches the Porter-Thomas one. Calling D * the depth after which XEB has reached unity (ideally D * would the depth after which | x|Ψ P | 2 corresponds to Porter-Thomas), we find empirically that Equation (28) could be used to estimate the actual fidelity F from XEB measurements. Figure 7 show an example of calculations contrasting the fidelity F with the XEB metric. Here we have used no truncation but added some noise on the two qubit gate so as to induce a finite fidelity per gate f . We find that both F and XEB decay exponentially with consistent decay rates. However, the large difference of the initial values at D = 0 leads to a shift of the fidelity which is significantly lower than the XEB curve. This shift increases as the fidelity is lowered and corresponds typically to one order of magnitude for a typical experimental value f = 99%.

V. RANDOM TENSOR THEORY OF ∞
We now turn back to the discussion of the asymptotic value f ∞ reached by the two-qubit gate fidelity in our calculations. The first remark of importance is that f ∞ is a property associated with a single tensor of the full MPS state: if we apply a gate between qubit i and qubit i + 1, only the associated T tensor defined in Eq. (10) comes into play. Since the whole goal of our quantum circuit is to scramble the wavefunction as efficiently as possible, a natural hypothesis is that the tensors M (i) and M (i + 1) become eventually well described by totally random tensors. In this section we explore this possibility and calculate the properties of the associated tensor T as well as the corresponding two-qubit gate fidelity f GTE . We find that the distribution of singular values of T obtained from the random ensemble closely matches what we observe in the MPS state.
In the spirit of random matrix theory [22,23], we introduce the Gaussian tensor ensemble (GTE) where a tensor M i µν is supposed to be totally random. The GTE can be sought as a "worse case scenario" where the quantum circuit is so chaotic that the tensors are left with no structure. In the GTE, the tensor M are distributed according to where the sum over ν spans 1 . . . χ, the sum over i spans 0, 1 and the sum over µ span 1 . . . βχ. In the remaining of this section, we restrict ourselves to β = 1 which corresponds to the tensors of Eq.(6). We shall have an example of β = 2 for the grouped-qubit algorithm we will discuss in section VI. From two such tensors, we apply a two-qubit gate following Eq.(8)-(12) constructing the associated tensor T and T and the SVD of T . From the 2βχ singular values S µ of T , we can obtain the associated fidelity f GTE through Eq. (15). Fig. 8 studies the distribution of the singular values S µ for tensor T obtained from the GTE. The singular values are sorted in order of decreasing magnitude and plotted as a function of the index µ = 1, . . . , 2χ. Plotting χS 2 µ as a function of µ/χ, we observe that all the different values of χ collapse onto a single curve. In other words, we find that there is some function g(x) such that This scaling is already valid for rather small values of χ. This observation can probably be put on firm mathematical grounds -it is consistent with the usual scaling of the semi-circular law for the GUE ensemble -but for the moment it is merely an empirical statement made from numerical evidence. It follows from this scaling that f GTE very quickly converges to .
In other word, one finds a finite value of the fidelity that is independent of χ. FIG. 8. Singular value S 2 µ of the matrix T obtained from the GTE ensemble. We find a perfect scaling of the form S 2 µ = g(µ/χ)/χ where µ is the index of the µ th singular value. The two bundles of curves correspond respectively to the CX ,CZ gates (two non-zero eigenvalues) and the iS π/6 /iS gates (four non-zero eigenvalues). Within one bundle, the different curves are indistinguishable.
other hand on the two-qubit gate used. Control-Z (C Z ) and control-NOT (C X ) are equivalent (they are related to each other through a change of basis of the second qubit) and corresponds to f GTE = 96.2%. Gates like the iSWAP gate (iS) or iSWAP followed by a π/6 rotation over the z-axis (iS π/6 , close to what is used in [4]) have 4 different singular values which roughly doubles the error with respect to C Z (f GTE = 93.2%). Fig. 9 shows how the distribution of the singular values in the GTE compares to the one obtained in the MPS simulation. We find a close agreement between GTE and the MPS simulations when looking at the T tensor for a gate in the center of the system and at large depth. The agreement is not perfect however, and we observe that the asymptotic fidelity of MPS simulations is always better than the one found in GTE, To try and understand why the inequality in Eq. (32) is not saturated, we plot in Fig. 9  therefore we never reach the "worse case scenario" of the GTE.
To summarize, f GTE can be thought as a lower bound for the fidelity found in the simulations for large enough χ (typically χ ≥ 300 in practice) and large enough depth. Getting beyond the asymptotic value requires algorithms that have an exponential cost. In the following section we describe possible strategies.

VI. ALGORITHMS FOR GETTING BEYOND ∞
The algorithm discussed above can also be used for 2D arrays, since any two qubit gates between distant qubits can always be written as a combination of gates on neighboring qubits using SWAP gates. However, this is inefficient and leads to a decrease of the effective f as the transverse dimension of the 2D array increases. Another limitation of the above algorithm is that one cannot efficiently simulate systems that have a fidelity above f ∞ .
There are multiple strategies that could be used to go beyond the above algorithm. In particular, recent progress in the algorithms for contracting tensor networks, such as [9] could be interesting candidates in 2D. Below, we follow a very simple strategy where we keep using MPS states, but group the qubits so that each tensor now represents several qubits.

A. Grouped MPS state
We now consider the MPS structure sketched in Fig. 1c where each tensor addresses several qubits. We now have P ≤ N tensors M (n) each addressing N n qubits with P n=1 N n = N . The tensors M (1) and M (P ) possess N n + 1 indices while the others possess N n + 2 indices, The number of elements of these tensors is χ 2 2 Nn so that the computing time now increases exponentially with the number of qubits per tensor. On the other hand, the two qubit gates that are performed inside a given tensor M (n) are now handled exactly, so that the average fidelity of a circuit increases.
To perform a two-qubit gate between neighboring tensors M (n) and M (n + 1), one proceeds in three steps. The first two are shown diagrammatically in Fig. 10. In the first step, one performs a QR decomposition of the two tensors to "extract" smaller tensors corresponding to the involved qubits. Assuming (without loss of generality) that the two qubit gate involves qubit N n of tensor M (n) and qubit 1 of tensor M (n + 1), one decomposes M (n) as where the "vectors" of Q(n) indexed by σ are orthonormal. The important point here is that the index σ takes only 2χ values. Similarly, we write: The second step follows Eqs. (8)- (12) of the algorithm of Section III with the replacement M (n) → R(n) and M (n + 1) → R(n + 1), and is shown for the present case in Fig. 10(b). In the last step the new tensors M (n) and M (n + 1) are obtained by contracting Q(n) with R (n) and R (n + 1) with Q(n + 1).
The main difference between the algorithm of Section III and the grouped MPS algorithm is that the resulting tensor T of Eq. (10) now has 4χ singular values instead of 2χ. As a result, upon truncation to keep only χ singular values, we anticipate that the fidelity per gate will be smaller than in the 1D case. However, as we shall see, this decrease will be more than compensated by the gain of having perfect gates within one tensor. In the terminology of random tensors, the grouped MPS algorithm corresponds to β = 2. For the C Z gate, the GTE fidelity drops from f GTE (β = 1) = 96.2% down to f GTE (β = 2) = 87.4%. . In (a) the grouped MPS tensors M (n) and M (n + 1) are exactly factorized using QR decompositions, such that the R(n) and R(n + 1) tensors carry the qubit indices acted on by the gate and the newly introduced indices σ and σ range over 2χ values. In (b) the gate acts on the product of R(n) and R(n+1), and the resulting tensor is factorized using an SVD truncated to χ singular values. Finally, to update the MPS (not shown), one computes the new tensors M (n) = Q(n)R (n) and M (n + 1) = R (n + 1)Q(n + 1) which diagrammatically looks like step (a) but in reverse.

B. Application to a two dimensional circuit
We now show the results of simulations performed on a 2D circuit. To put the results into the perspective of what can be achieved experimentally, we choose a circuit very close to the one used by the Google team in their "supremacy" experiment [4]. We consider a 2D grid of 54 qubits as shown in Fig. 11a. The circuit is shown in Fig. 11b and alternates one-qubit gates applied to each qubit (same distribution as in the 1D case) with two-qubits gates (Control-Z) applied on different pairs of qubits according to the color shown. Except for the choices of one-and two-qubit gates, and the number of qubits (53 versus 54), the setup is identical to the "supremacy sequence" of the Google experiment [4]. In Ref. [4] a XEB fidelity B = 0.002 was reached after a depth D = 20 corresponding to a total of 430 two-qubit gates. Ignoring the difference between XEB and the fidelity F, this translates into av = 1.4% which we shall use as our reference value to evaluate the performance of the grouped MPS algorithm. Fig. 11c shows various strategies for grouping the qubits. The [1] 12 grouping corresponds to 12 tensors that contains one column of qubit each (i.e. alternatively 5 and 4 qubits). The [6,6] grouping is the most expensive computationally with two tensors of 27 qubit each. Note that the tensors on the edges are less computationally costly than the middle ones, since they only have one bond index. The results of the simulations are shown in Fig. 12 for a depth of D = 20. While the error rate is significantly larger than in the 1D case, we find that it can be brought down to less than 1.4% (which corresponds to a global fidelity of F = 0.002) on a single core computer. The computing times of the data points of Fig. 12 range from a few seconds to less than 48 hours for the most expensive points on a non-parallel code (single core calculation). We find that the grouping strategy is effective, but not as efficient as the maximum gain that one could expect: even though some of the gates become perfect upon grouping, we observe a decrease of the fidelity for the noisy gates which reduces the overall gain. For χ = 320 and the [4,2,2,4] partition where the final fidelity is slightly better than F = 0.002 (see Fig. 12), the memory footprint of the calculation is 4.5 GB of memory which represents only 1.5 × 10 −6 percent of the size of the total Hilbert space spanned by the 2 54 qubits.
To conclude this section, we have shown that for the Control-Z gate a simple grouping strategy allows one to reach the same fidelity as the Google experiment [4] in a matter of hours on a single core computer (i.e. f av ≥ 98.6%). Note that the Google experiment was not performed with Control-Z but with more complex gates that produce more entanglement. (In the experiment a different choice of gates was used for each pair of qubits such as to optimize the fidelity.) Reaching a similar fidelity for such gates is beyond the possibility of a single core computer with the present algorithm; it would require a parallel implementation that we leave for further investigations.

VII. DISCUSSION
In this work, we have discussed a practical algorithm that allows to simulate a quantum computer in a time which grows linearly with the number of qubits N and the depth D at the cost of having a finite fidelity f . The fidelity f can be increased at a polynomial cost up to a finite value f ∞ ; increasing it further has an exponential cost in the fidelity. Our main observation is that fidelities of the order of 99%, which are typical fidelities found in state of the art experiments, can be reproduced at a moderate computational cost.
Is a fidelity of 99% large or small? From an experimental physics perspective, it is certainly quite an achievement to keep several dozen qubits at this level of fidelity. From a quantum information and classical algorithms point of view, a question is what is the level of entanglement-hence the actual fraction of the Hilbert space that can truly been accessed-associated with this level of fidelity. Our MPS ansatz can provide an estimate (or at least an upper bound for one may come up with better algorithms) for this fraction. Since the FIG. 11. a) Sketch of the quantum circuit with 54 qubits in a 2D grid. The qubits are represented bu the black dots while the two-qubit gates by the color links. b) The circuit alternates one-qubit gates (black dots) with two-qubit gates (here the Control-Z gate). The depth D counts the number of two-qubit gats per qubit. c) Different grouping strategies for the group MPS algorithm. [1] 12 corresponds to a grouping in 12 blocks counting 1 column each; [4,2,2,4] corresponds to a grouping in 4 blocks counting respectively 4, 2, 2, and 4 columns.
MPS ansatz only spans a very tiny fraction of the overall Hilbert space, it follows that the computational power associated with fidelities in the 99% range is much more limited than the full size 2 N of the Hilbert space would suggest. We conclude that increasing the computational power of a quantum computer will primarily require increasing the fidelity/precision with which the different operations are performed [24]. Secondarily, one could try to improve its connectivity with e.g. quantum buses [25] as we have seen that 1D simulations are far easier than 2D ones. However, increasing the number of qubits will remain ineffective until better fidelities have been reached.
As a side comment, our approach could also be used to get lower bounds for quantum error correction (QEC) schemes [26]. Suppose that for a certain connectivity, one has an algorithm that can reach a fidelity f in polynomial time in N and D. Then, it is reasonable to expect that any QEC code has a threshold p > f . If it were not the case, one could build a logical quantum computer with a classical one at a polynomial cost by simply simulating the QEC protocols on the classical computer. In this respect, extending our approach to a truly 2D algorithm (beyond the quasi-1D one discussed in this article) would be particularly interesting. Indeed, 2D surface codes have a particularly low threshold p ≈ 99%. How close to f = 99% can one get at a polynomial cost in 2D is currently an open question.
Finally, it would be interesting to perform a similar study, but of the practical approximability by MPS of circuits designed for useful tasks. Goals could include estimating minimum fidelities needed to perform these tasks with a high probability of success and finding crossovers where useful quantum algorithms could offer advantages over classical approaches.

ACKNOWLEDGMENTS
XW and YZ thank the Flatiron CCQ where this work was initiated during summer 2019. XW acknowledges funding from the French ANR QCONTROL and the E.U. FET open UltraFastNano. Numerical results involving MPS were obtained using the ITensor library [27]. The Flatiron Institute is a division of the Simons Foundation.


extfieldsofstudy:
Medicine
Computer Science

text:
Efficient goal attainment and engagement in a care manager system using unstructured notes

Abstract Objective To improve efficient goal attainment of patients by analyzing the unstructured text in care manager (CM) notes (CMNs). Our task is to determine whether the goal assigned by the CM can be achieved in a timely manner. Materials and Methods Our data consists of CM structured and unstructured records from a private firm in Orlando, FL. The CM data is based on phone interactions between the CM and the patient. A portion of the data has been manually annotated to indicate engagement. We present 2 machine learning classifiers: an engagement model and a goal attainment model. Results We can successfully distinguish automatically between engagement and lack of engagement. Subsequently, incorporating engagement and features from textual information from the unstructured notes significantly improves goal attainment classification. Discussion Two key challenges in this task were the time-consuming annotation effort for engagement classification and the limited amount of data for the more difficult goal attainment class (specifically, for people who take a long time to achieve their goals). We successfully explore domain adaptation and transfer learning techniques to improve performance on the under-represented classes. We also explore the value of using features from unstructured notes to improve the model and interpretability. Conclusions Unstructured CMNs can be used to improve accuracy of our classification models for predicting patient self-management goal attainment. This work can be used to help identify patients who may require special attention from CMs to improve engagement in self-management.

INTRODUCTION
Care management is a collaborative, patient-centered approach to managing patient health conditions. 1 In 2015, the US Centers for Medicare and Medicaid Services began reimbursing non-face-to-face care management and coordination services for certain Medicare beneficiaries with multiple chronic conditions. 2 Globally, a similar trend has also been pushing the creation and reimbursement of similar health services for better integrated care in countries such as Germany, Ireland, and the United Kingdom. [3][4][5] An essential role in care management is that of the care manager (CM), who coordinates with other clinicians, as needed, to set appropriate self-management goals for patients, and who also coaches the patient toward achieving those goals. A CM is usually a licensed nurse, social worker, or other certified specialist. Care management can be delivered to the patient in various settings (eg, at home, in clinic) and via different modalities (eg, telephone, video conference, SMS, chatbot, postal mail, email or other messaging systems). In this work, we focus on the situation where patients have either been recently discharged from the hospital and require transitional care management, or who are self-managing a chronic disease indefinitely. In both situations, the patients in our study are being contacted by a CM on a regular basis, via telephone. We refer the reader to our prior work for further details on the care management model used in our analysis. 6,7 Peikes et al. 8 provide a more general description of care management models used in practice.
One aspect of care management is measuring how often selfmanagement goals are attained. For example, a typical goal for patients who are newly diagnosed with diabetes is to educate themselves about their disease; this includes learning how to recognize disease symptoms and understanding how to perform relevant disease management and medication regimens. Typically, the more engaged a patient is, the easier it is for the CM to coach them toward their goals. The meaning of patient engagement is widely discussed in the literature, [9][10][11] and not surprisingly, may be defined in a variety of ways to accommodate the different contexts and stakeholders involved. In our work, we consider a patient to be engaged if the CM reports having had positive or constructive communications with the patient, or reports that the patient is taking specific actions intended to promote their own health. The objective of our work is to support CM decisions by predicting if a patient is engaged or not engaged to participate in their own care, and whether they will efficiently or inefficiently attain an assigned self-care goal. Henceforth when we refer to our model predicting engagement we are referring to both engagement and lack-of-engagement and predicting efficient goal attainment as both efficient and inefficient goal attainment.
CMs typically document each encounter with the patient in electronic care management systems. The CM's documentation, or records, may include unstructured, natural language notes, as well as more structured entries for the date, time and mode of communication, the patient's health status, goals and interventions that may have been assigned, and the patient's progress against those goals. By analyzing both structured and unstructured elements of the CM's records, we develop models for predicting efficient goal attainment. In particular, we are interested in analyzing CM notes (CMNs) because they often contain cues that indicate the engagement level of a patient to their goals. An example of engagement-bearing language might be "patient taking the medication as prescribed", while an example of non-engagement-bearing language might be "She says she did not like the way the medication made her feel so she has stopped taking it". We hypothesize that these cues can help detect the engagement level of a patient and whether efficient goal attainment (and therefore better health outcomes) can be expected.
Furthermore, this work aims to provide support to the CM in the cases where a goal is not being obtained efficiently. Providing extra guidance in these cases can help the CM assign new goals that are more likely to result in a positive outcome. Some anecdotal examples are (1) a patient may express that they have been missing follow-up appointments due to lack of transportation can guide the CM to assign the implementation goal or (2) a diabetic admitting to not following their strict diet can indicate that education and selfcare goals could be important.
In this article, we focus on answering 2 key questions: First, whether the engagement level of a patient can be determined from what is recorded in CMNs; and second, whether the task of predict-ing efficient goal attainment can be further facilitated using the engagement-related signals extracted from CMNs, beyond what has been captured from the structured entries of CM transaction records. Our contributions are: • We identify an opportunity to leverage unstructured data (text) from CMNs to improve learning models to assist in care management. • We combine structured and unstructured features to develop models for predicting efficient and inefficient patient goal attainment. • We build on prior work to create an engagement model with significant improvements in performance using domain adaptation techniques and BERT (Bidirectional Encoder Representations from Transformers) 12 to generate cues and unstructured features for the efficient goal attainment task.

RELATED WORK
We focus on 2 areas of related work: learning patient engagement from unstructured notes, and patient engagement and goal attainment for care management.

Learning patient engagement cues from unstructured notes
Previous studies have demonstrated the application of natural language processing (NLP) techniques for capturing relevant information from clinical notes taken during clinical visits (including both physician and nurse notes, as part of the patient's clinical records). Examples include: (1) identifying patients with specific diseases 13 ; (2) monitoring adverse events as a patient safety surveillance tool 14 ; (3) supporting clinical decisions to manage risk around chronic conditions 15 ; (4) predicting readmission and phenotyping from discharge summaries 16 ; (5) extracting health quality information (eg, identifying care gaps) 17 ; (6) extracting problem lists to improve clinical work productivity 18 ; (7) assessing doctor compliance, sentiment, and adherence (eg, compliance to tobacco cessation guidelines) 19 ; and (8) protocol compliance in discharge summaries. 20 Among these, only a few investigate linking information from notes with structured records. For example, Watson et al. 21 link the social health determinants identified from both structured records and clinical notes to predict re-admission. CM records, on the other hand, capture information about a patient between these clinical visits and hospital stays and can provide insight into the self-management activities of the patient in the home (ie, non-clinical) setting. Lopez et al 22 Explore consolidating and highlighting relevant information from multiple care management and clinical notes but they do not specifically address engagement. Other work in care management data analytics has been used to identify higher priority patient cohorts (eg, high-cost, high-need patients) 23 and to surface social determinants of health along with clinically relevant information at the population (or cohort) level. 24 These applications of CM data analytics have not fully explored the potential of using care management records (especially CMNs) to enhance CM work productivity and increase patient understanding at the level of the individual. Previous studies show that using informatics tools to personalize health communication with patients is important to patient engagement. 25,26 Evidence has also shown that patients who are more engaged have better health outcomes and care experiences. 27 While there exists work dealing with sentiment in clinical notes, such as positive or negative affect, 28 and speculative language, 29 lack of engagement cannot be reduced to sentiment. For example, lack-of-engagement bearing language can also contain positive sentiment: "patient is feeling better so she has stopped taking her medication". Topaz et al. 15 developed a document level discharge note classification model that identifies the adherence of a patient in the discharge note. However, they focus only on the lack of adherence, specifically, toward medication, diet, exercise, and medical appointments. In contrast, we follow prior work and also examine the quality of the patient's communication and relationship with the CM, which may be another indication of engagement. 30 Patient engagement and goal attainment for care management Previous work has shown that goal attainment is important to the implementation of health behavior change and can serve as a proximal proxy measure of patient health outcome in the longer term. [31][32][33] In the domain of care management, previous work has focused on learning individual-level care planning strategies from practice by the Behavioral Response Inference Framework, 6,7 which outperformed population-level strategies in the task of delivering more accurate intervention recommendations for goal attainment. In other domains, such as social media analytics, goal attainment records have been constructed from social media messages using NLP techniques to understand action-outcome relationships and the propensity of a user for taking actions to achieve health outcomes. 34,35 However, to date, no other studies have investigated how to leverage NLP approaches to predict the attainment of health goals, where these goals are primarily attained through the active engagement of the patients themselves.
In our work, we aim to bridge the gap by first understanding how to extract engagement cues and quantify engagement level from unstructured CMNs. Then, we combine the extracted signals with other goal attainment-related features from care management records to determine what the potential is for efficient goal attainment under current engagement and intervention strategies.

DATA
Our first dataset (referred to as the GOAL dataset) was curated from a private, not-for-profit healthcare network in the southeastern United States over a 24-month period from 2015 to 2017. It con-tains records of patients recently assigned to a disease management program or a transitional care program after being discharged from the hospital (disease management programs focus on addressing chronic care; transitional care programs aim to reduce hospital readmissions). The CM records contain goal attainment transactions across 30 different goals in 6 major focus areas. The entire dataset consists of 4504 transition of care and 440 chronic care patient interactions. In order to ensure a good sample of language use in engagement and goal attainment, we restricted the analyses to those records that contain at least one non-empty CMN, giving 2710 goal attainment records from 1882 unique patients' care plans. Repeated encounters for a particular patient for a particular goal were aggregated together into a single note. The GOAL dataset consists of 2 parts: (1) structured CM transaction records and (2) unstructured CMNs. From the 2710 records, we obtained goal attainment history from the structured entries of the records. A total of 2363 goals were attained efficiently (ie, in less than or equal to 2 weeks). Three hundred and forty-seven goals either were not met or took more than 2 weeks to complete, with some taking more than 180 days to complete.

Structured CM transaction records
The CM records include structured information gathered by the CM in the following 4 categories for each patient: (1) patient-specific information (eg, age, gender); (2) CM program experience (eg, how many care programs have been assigned to the individual, what type of care program); (3) call-specific (eg, on which day of the week was the call made); and (4) goal and intervention assignment (eg, what type of goal-focus area, short-term vs. long-term-and whether it is a priority). Note that any given goal can have multiple interventions being assigned for its attainment. A summary of the GOAL dataset statistics for each of the structured data categories is shown in Figure 1.

Unstructured CMNs
In addition to recording structured information, CMs record notes based on phone calls with the patient. To answer the 2 main questions in this study, we follow the notion of patient engagement from CMNs described in previous work 30 but take a different approach in our model and setup. Although we cannot include an actual note, we provide some example sentences in Table 1.
Recent trends in medicine have focused on the role of patient behavior and lifestyle choices in positive health outcomes. 36,37 Figure 1. Summary statistics of the GOAL dataset. Efficient goal attainment is defined as achieving the assigned goal in less than 2 weeks.
As described in prior work, 30 specific behavioral characteristics of patient engagement that we identified in the notes included whether the patient was reported to have had constructive communications with the CM (ie, engaged with CM) and whether the patient has taken specific actions to promote their own health (ie, engaged with care); we annotated the GOAL dataset accordingly for engagement or lack-of-engagement in the CMNs on the sentence level. A description of the data labels is shown in Table 1. (Although the labels in the dataset distinguish between patient engagement with care and patient engagement with the CM, we do not make a distinction in the target of the engagement in our classifier. 30 ) These annotations were done in-house with detailed feedback from practicing CMs and experts in care management solutions. In the annotation process, multiple rounds of cross-evaluations were employed to ensure the consistency of labeling. The amount of data that was labeled as engagement (409 sentences) or lack-of-engagement (331 sentences) is relatively small with 740 sentences in total. This is because most sentences do not indicate patient engagement. While Rosenthal and Faulkner 30 included the class "other", we chose not to include this class because its frequency dominates the model during training. Instead, we trained and tested the model only on data with engagement or lack-of-engagement labels. To address the small data size, we obtained a large amount of engagement text freely from tweets in a health-related Twitter dataset. 38 We automatically labeled 128k tweets from the Twitter dataset with engagement (118k) and lack-of-engagement (10k) by looking for words such as "take" and "keep" for engagement and "refuse" and "deny" for lack-ofengagement.

Method
To answer the 2 motivating questions, we have defined 2 tasks for which we train models: (1) Engagement classification based on unstructured CMNs; (2) Efficient goal attainment classification based on both engagement features from unstructured CMNs and structural features from CM transaction records.

Engagement classification
Our first task is to classify the sentences in CMNs as signaling engagement or non-engagement behavior using the GOAL and Twitter training datasets described in the Data section. The test dataset contains data from the GOAL dataset only.
We experimented with classifying engagement using 3 different models. The first is a support vector machine (SVM) model-a traditional feature-heavy machine learning approach used in prior work. 30 We experimented with the same 6 groups of features: ngrams and parts-of-speech, embeddings, lexico-syntactic (words and dependency tuples), lexical-stat (word statistics, such as sentence length and word lengths), sentiment, and medical (identifiable medical concepts). We used the python scikit-learn SVM linear model. 39 As in the prior work, we explored domain adaptation, in this case using the health-related Twitter dataset as the out-of-domain data. 38 Following the approach of Daum e, 40 we used domain adaptation with each feature duplicated for the target and source languages, with the feature only turned "on" for the target language. One major difference between our experiments and those reported in prior work is that we excluded the "other" class during training. Our second approach uses deep learning, specifically, a recurrent neural network (RNN) model with attention implemented in TensorFlow. 41,42 In our model, we used attention to generate a weighted sum of GRU cell outputs for each word in the input text, to focus the model on those words that are the most useful for prediction. We used the Adam optimizer, a batch size of 128, dropout of 0.2, learning rate of 0.001, and an embedding size 300 for 200 epochs. Finally, several recent studies have shown that using the pre-trained language model BERT 12 significantly improves performance of down-stream tasks. The BERT model is the state-of-the-art language representation model that pre-trains bidirectional representations by jointly conditioning on both left and right context. In our setting, we fine-tune the BERT model on our engagement training data and take the output for the first token in the input (ie, the special [CLS] word embedding) as the representation of the input. It is then used for label prediction by feeding into a classification layer. For our BERT experiments, we used a PyTorch implementation (https://github.com/huggingface/pytorch-pretrained-BERT) with the bert-baseuncased model. We used the default BERT parameters including the BERT Adam optimizer, a batch size of 32, dropout of 0.1, and embedding size 768. All text was cutoff to the first 128 word-pieces and we ran it for 3 epochs.

Efficient goal attainment classification
Prior work focused on general goal attainment which was defined by a structured field indicating that the goal was met or not met. 25,26 The problem with using this field is that a goal could take 6 months to complete. While the goal might have been attained eventually, it might not be the best choice to recommend to the target patient. Therefore, our second task is to predict whether a goal specified in a CM record can be achieved efficiently. We define efficiency as a goal being completed in less than or equal to 2 weeks, which is the usual period of time CMs are instructed to spend attempting to encourage individual patients to achieve a particular goal. Even though we define this task as efficient goal attainment, being able to predict the goals that will not be completed efficiently is just as important (if not more so), because the CM should focus "Patient disappointed by lack of weight loss but is just beginning exercise regimen"; "Patient joined book club." Engagement with care manager Adherence to a doctor or CM instruction or understanding of CM advice.
"Patient verbalized understanding"; "Patient confided that she has gaps in nitroglycerin use." Lack of engagement with care Lack of engagement by using language suggestive of nonadherence to guidelines, health-adverse behavior, lack of social ties, or negative impression of patient self-care.
"White female, disheveled appearance"; "Patient admits to 'sedentary' lifestyle." Lack of engagement with care manager Non-adherence to a prescribed instruction or a negative response to interaction.
"Patient rude during call"; "Patient angrily refused further outreach." on these patients. Predictions of inefficient goal attainment would be surfaced to the CMs when they reach out to the patients, so as to facilitate shared decision making on how to intervene for achieving an assigned health goal. We first processed the structured call records data and fed it into our pipeline to identify the differentiating factors for goal attainment. The key components of the pipeline are: (1) extract the behavioral features in an online dynamic fashion from the call records, (2) extract the engagement features and n-grams from the CMNs, and (3) perform an outcome-driven feature projection using locally supervised distance metric learning. 43,44 We generated 4 groups of features: struct: 25 structured features (Since we are predicting the efficiency of goal attainment in this task, we did not include any structured data that overlaps with efficient goal attainment (eg, whether an assigned health goal has passed its due date is directly correlated to the structured field used to compute efficient goal attainment.) such as gender, age, and goal focus areas. All features are shown in Figure 1.
eng: The best engagement model (BERT) was used to generate 8 engagement features. We generated the max, count, median, and mean scores for both engagement and lack of engagement per note by running the model on all of the train and test sentences in the notes.
eng_n-gram: In addition to the eng features we also retained the sentences from the engagement model that were representative of engagement and lack-of-engagement to explore important words from each class.
n-grams: The most frequent words and pairs of words from the unstructured notes.
The combined structured and engagement features make up our patient representation for efficient goal attainment outcome and allow for an interpretable model that can provide the CMs with meaningful insight for assigning goals to patients. We used these features in a linear SVM model using scikit-learn. 39 The pipeline of the entire system is shown in Figure 2.

RESULTS
In this section, we describe in detail the results for our 2 models: engagement classification and efficient goal attainment classification.

Engagement classification
The engagement results for each model are shown in Table 2. Experiments were performed on a held-out test set of approximately 20% of the data. We explored different permutations of features for the SVM model, but using all of the features worked best so we include only these results in the table. Exploiting out-of-domain Twitter data with the SVM shows significant improvement, from 85% to 89% average F-score. On the other hand, applying transfer learning using Twitter data with the RNN does not provide any improvement. Although the RNN model does perform slightly better than the SVM model with just CMNs, the SVM model trained with Twitter data outperforms the RNN model. We expect this is due to the very small size of the in-domain data. Deep learning approaches tend to perform better when a large amount of data is available. Finally, using the BERT model fine-tuned on the CMNs gives us significantly better results compared to both the SVM and RNN, with an average F-score of 95%.

Efficient goal attainment classification
We trained an SVM model using different combinations of features as the training feature sets and used the development feature set to  tune the model parameters. We ran experiments with 2 baselines and the 4 feature groups described in the previous section: struct, eng, n-grams, and eng-n grams. We compare our model against a majority and minority baseline: majority baseline: predict that all goals are attained efficiently ( 2 weeks). minority baseline: predict that all goals are not attained efficiently.
Due to the small size of our dataset and class imbalance we chose to perform 5-fold cross-validation and report the average results over the 5 folds. Although we report accuracy, this is not an ideal measure in this case because we want to find the goals that cannot be met efficiently. Therefore, we also report precision, recall, and Fscore. We show performance on each class, efficient goal attainment ( 2 weeks) and inefficient goal attainment (>2 weeks), as well as the macro-average of the 2 classes. Although we provide the results for each class, the accurate picture of our systems' performance is the average precision, recall, and F-score. This stems from the need not only to predict goals that are met efficiently (which could be done with high accuracy by predicting the majority class), but also to find goals that cannot be met efficiently. Statistical significance was computed using McNemar's test.
In Table 3, we show various combinations of the feature groups and also compare to the baselines. It is important to note that the 2 weeks baseline does very well because of the class imbalance. However, this baseline does not predict any of the >2 weeks instances correctly (our aim is to find these rare cases of inefficient goal attainment). In all cases, we significantly beat the majority baseline in average F-score. Furthermore, the 3 models that combine struct and engagement features significantly beat the model using just the struct features. Our best result is to include the structured, engagement, and n-gram features. This combination gives an average F-score of 0.66. These results indicate that combining engagement with the structured features does help and that the unstructured notes provide important cues to engagement and efficient goal attainment. It is also worth noting that the classifier n_grams, which uses only ngrams as features (without any structured features) performs very comparably to the classifier struct, which uses only structured features. This indicates that the n-grams are informative on their own.
Looking at the top structured features that the SVM correlated with the prediction for both classes in the baseline model for all the folds, we found that the focus areas educational, self-care, reducing risks, and medications were always correlated with efficient goal attainment, whereas other and implementation were always correlated with inefficient goal attainment. Goals that were marked as high priority and long term were also indicative of efficient goal attainment. On the other hand, number of care programs assigned and having no priority set were indicative of inefficient goal attainment. Both of these can indicate a lack of response from the patient.
We find that general n-grams performed better than including ngrams based on the engagement model. We expect this is because there are overlapping words in both classes. The SVM model learns how to distinguish between the words regardless of the prediction for the sentence. To show these observations, we looked at the top 10 features per class of our best model (struct þ eng þ n-grams) for each of the folds to see which n-grams (words or bi-grams) occurred most frequently in each class. These n-grams are shown in Table 4. Many of the top n-grams in the 2 weeks class involve successfully performing the "welcome home call" (eg, "wh spoke") indicating a responsive patient. Many of the top n-grams in the >2 weeks class are connected to the patient saying or admitting something (eg, "patient admitted"). These can indicate that the patient admitted that they were not complying or were not interested in their goals. These words can be cues and provide insight to the CMs as to whether the assigned goal and intervention were successful for the patient. Table 3. The 5-fold cross-validation results for efficient goal attainment prediction in terms of accuracy, precision, recall, and F-score for the structural (struct), engagement (eng), n-grams, and engagement-oriented n-grams (eng_n-grams) groups of features Note: All models significantly beat the Average F-score for the baselines and the underlined models significantly beat the Average F-score of the struct model with P-value 0.001. The boldface values indicate the highest score in each column. Note: The acronym expansions provided in parenthesis are shown for clarity but do not appear in the notes.

CONCLUSION
In this article, we hypothesized that we could predict efficient goal attainment with greater performance than a proposed baseline model. Furthermore, we explored using engagement features derived from unstructured CMNs for improving the prediction of efficient goal attainment, compared to using only features derived from structured care management records. To test our hypothesis, we trained models for patient engagement classification and models for efficient goal attainment classification.
Comparing the engagement models we implemented showed that the BERT model outperformed models that were pre-trained on an external cheaply labeled data set (RNN and SVM). We note that the performance of the latter models were still very reasonable (ie, F-scores > 0.8). We conclude that transfer learning approaches are worth exploring in this setting.
Results of our efficient goal attainment experiments showed that the (F-score) performance of our prediction models outperformed the majority baseline model by around 40%. This performance improvement can be attributed to the ability of our models to improve the precision associated with detecting inefficient goal attainment. Predicting inefficient goal attainment is challenging in this dataset because these events constitute a minority of the events in the data. In practice, however, identifying these instances could have an impact on the practice of care management, by helping CMs to identify patients that are at greater risk for not achieving their goals. These patients may benefit from more extensive assessment and interaction with CMs. Our findings show that the improvement when incorporating engagement features from the unstructured notes is statistically significant compared to models using features from structured data alone. Second, we found that our n_grams model performed comparably to our struct model, and considerably better than our eng_n_grams model for predicting goal-attainment. Since the n_grams model was not restricted to sentences indicating engagement, our finding is consistent the findings of Lopez et al., 21 which learn non-engagement-related patient attributes from care notes.
Aside from being useful for predicting efficient goal attainment, the classification of engagement is independently useful for surfacing specific engagement strengths/weaknesses of the patient that could be addressed. In particular, the aspects of engagement that our models can detect would be useful for highlighting potential issues in the quality of the communications between the patient and the CM, or specific health behaviors that could be further encouraged or discouraged. Inspection of the cues in unstructured text may even provide insight to the CMs that are suggestive of the types of goals and interventions that could be most appropriate. In the future, we intend to expand our analysis by clustering patients to discover the types of goals and interventions that may be most appropriate for patients from each cluster.

AUTHOR CONTRIBUTIONS
SR, SD, P-YSH, KB, and C-HC were involved in study design and data preparation/annotation. SR implemented the NLP-based engagement classification, domain adaptation, and transfer learning models. SD and P-YSH were involved in structured data analysis and feature engineering. SD, SR, and P-YSH implemented the code for efficient goal attainment. All authors were involved in interpretation of the results and drafting/revising the manuscript. All authors have approved the final manuscript.


Understanding Smart Wearable Sensors Technology: Impact on Human Health and Fitness

In the field of health care management, smart wearable devices and its supporting technologies have tremendously made a name all around the globe. Smart watches and other sensor trackers are practically being used by various people and its usage has shown to be accompanied with lots of benefits. This technology was envisaged to play a vital role in the healthcare needs of people; especially with applications in the healthcare sector. The objective of this study, therefore, is to evaluate the technological impact of wearable sensors in human health and fitness (HHF). A web based survey was used for data collection for the period of one month. Emails were sent to registered members of a particular gym who uses any of the smart wearable sensors in keeping fit. The study findings indicate that among the smart wearable devices examined, smart wristwatches (45.6%) appears to be the most commonly used wearable sensor device followed by smart wrist bands (34.7%), smart textiles (10.7%) and smart rings (9.1%). This signifies that a large number of people can effortlessly use SWSs and devices and are optimistic about its support in their daily healthcare/fitness needs. Users are positive on the technological prospects of SWSs and devices; although there is a gap between personal motivation to use wearable devices and trust in the confidentiality and privacy of data generated. DOI: https://dx.doi.org/10.4314/jasem.v24i7.19 Copyright: Copyright © 2020 Idoga and Adamu. This is an open access article distributed under the Creative Commons Attribution License (CCL), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Dates: Received: 16 May 2020; Revised: 29 June 2020; Accepted: 07 July 2020

The advent of affordable and efficient portable sensors is attributed to different factors, one of which is the introduction of wireless communication networks (Kwee-Meier et al., 2016;Lee et al., 2016). Sensors have the ability to dictate, process and transmit different signals, as a result, they are used by healthcare professionals to monitor the patient's health. The resultant effects which are, the development of smart wearable sensors, electronics or advanced technologies using computers (De-Acutis and De-Rossi, 2017). Smart wearable sensors (SWSs) refer to electronic tools that are translated into items that can be preprocessed into the body with enhanced computing devices that grant/process inputs (Kwee-Meier et al., 2016). SWSs could be used by attaching on clothing, patches in the skin, wristwatches and wearable glasses. However, recent studies have shown that SWSs can also be inserted into the body of a patient via surgical procedures (Chan et al., 2015).
Another key feature of SWSs is its hands-free function that could enable users to monitor their health with relevant data while performing their daily routine (Woollaston, 2017;Kaewkannate and Kim, 2016). Some other characteristics include; access, comfort, portability, general multi-functions, importance, reliability of use, and practicability in real time. Consequently, according to Ritevski and Chen (2018), some SWSs such as the Insulin Monitors (INM) and Cardiac Event Monitors (CEM) has been provided freely by laws governing the healthcare body.
SWSs has been seen to be of great benefit to the wellbeing of the user, hence some are designed in the form of simple fitness tracker with tracking capabilities as well as accessing and monitoring user's physical activities which are in line with medical fitness and wellness of patients Lee et al., 2016). Significant parameters such as, the heart-beat rate, the blood pressure (BP), the pulse rate, muscle actions, sugar and glucose level, electrocardiogram (ECG), body temperature, digestion of oxygen saturation, the stress levels and eating habits are measurable by SWSs (Jayoung et al., 2018). Each of these parameters requires a certain type of sensor at a specific part of the human body. The goal of this study is to investigate the technological impact of SWSs in human health and fitness (HHF). Fitness wearable sensors (FWSs) are used in tracking and accessing personal health and daily routine checks. The potentials in SWSs has necessitated the massive boost in the technology sector, resulting in the production of fitness SWSs such as smart rings, wrist bands, wrist watches and smart textile sensors, etc. (Witte and Zarnekow, 2019). In this study, we shall consider the above named fitness SWSs.
Smart rings (SRs): Smart rings (SRs) are one of the many finger augmentation technologies. They are made of electronic contraption and sensors and mostly worn on the fingers. Other finger augmenting technologies include the numerical gloves and finger nails display. SRs has input/output competences in which they are able to detect motion, gestures, muscle activities and provide feedbacks (Gheran et al., 2018). Incorporating physical checks together with wearable technologies requires sensor placement. Hence, Asada and friends proposed the smart ring for the analysis of heart rate and blood oxygen saturation (Porciuncula et al., 2018).

Smart wrist bands (SWBs):
Smart wrist bands (SWBs) consist of numerous sensors capable of sensing motion, temperature, pulse and other vital signs measurement. SWBs was first used on athletes to monitor their heart rate performance in real-time during an exercise routine (Koydemir and Ozcan, 2018).
Smart wrist watches (SWWs): Smart wrist watches (SWWs) are embedded with several sensors for keeping track of a user's fitness and health metrics as regards blood pressure, heart rate, calories burned, number of steps taken, blood glucose and sleep quality (Miller, 2019).

Smart textiles (STs):
Smart textiles (STs) are used to monitor the physiological vitals of users. STs such as smart socks provide 3D measurement of pressure distribution of the user's whole foot while walking. This collects vital information of the user and enhance tailored fabrication of shoes for diabetic foot syndrome patients, thereby, reducing pain in the foot and subsequent foot ulcer (Koydemir and Ozcan, 2018).
Despite the many benefits such as remote monitoring, fitness tracker, CEM, INM etc. (Ritevski and Chen, 2018) associated with SWSs, some users still believe that the technological impact of these devices is negligible especially in HHF. Therefore, this study aims to evaluate the technological impact of SWSs in HHF.

MATERIALS AND METHODS
This is a closed, voluntarily web-based survey. As stated earlier, a web-based survey platform (WBSP) (https://www.surveymonkey.com) was used in questionnaire design and collection of data. The questionnaire was anonymous and protected by Norton and TRUSTe with approximately ten (10) minutes to complete. The WBSP clearly shows progress indicators and personal comments for any of the questions entered by the compilers. According to a "Checklist for Reporting Results of Internet E-Surveys" (CHERRIES) (Masconi et al., 2019), all questions are compulsory. Based on this checklist, only completed questionnaires were examined exclusive of questionnaires with omitted data. While on the WBSP, it is possible to go back to a previous page through a "back button" in order to reverse answers before submitting. Answers were automatically collected on the Survey-Monkey database.
Questionnaire development: The questionnaire used in this study was adopted from the study of Mosconi et al., (2019) and administered through Survey Monkey -a web-based survey platform. Adequate caution was taken to ensure the questionnaire items consist of words such as frequency of use, mostly used, utilities, issues associated with use, as well as the technological impact in relation to healthcare technologies focusing on HHF wearable sensors. Prior to the distribution of the questionnaires to participants, a pretest of the questionnaire was presented to knowledgeable experts in the field of HHF and eHealth technologies: this is to ensure clarity, completeness and necessary suggestions. Their response/consensus resulted in the final questionnaire that was used in the study.
Participant's selection: Participants of the survey were registered members of a gym center in Nigeria (N = 398) who are users of any of the SWSs mentioned above. The gym center was considered appropriate for the survey as a result of its relentless advocacy on the necessity of wearable devices for its members in keeping track of physical activities and maintaining a good fitness level; especially, for those with underlying chronic diseases (Pardamean et al., 2019). The survey URL link was sent through emails to the participants through their email addresses provided at the time of membership registration. Participants were asked to first, give their consent before proceeding with the survey. Additional care was taken to ensure that the duplicate and wrong email addresses as well as non-users of wearable sensors were eliminated (n= 23). A reminder email and follow-up call were also given to each of the participants two weeks later. The whole process of the survey took a month approximately (01 February -02 March 2020).

IDOGA, EP; ADAMU, AI
Data analysis: Statistical Analysis System (SAS version 9.4) was employed to carry out a descriptive analysis of collected data. By considering suggestions from an earlier study (Mosconi et al., 2019), pattern of answers by respondents were analyzed by their age and personal use of wearable sensors. Only results with substantial patterns in a set alpha level of 0.05 was considered for a P value evaluation.

RESULTS AND DISCUSSION
A total of 375 responses was collected, with a response rate of 94.22% (375/398). Data analysis was conducted on 375 correctly filled questionnaires since 23 of the responded data was insufficient to be considered in the analysis. The Table 1 summarizes the respondent's characteristics. Out of the 375 responders who participated in the survey, 110 (29.3%) were male, while 265 (70.7%) were female respectively. Indicating that, in terms of health care technological advancement, women are well knowledgeable and represented while the men are fairly represented. Respondents were aged 18-60 with the mean age of 39. An appreciable level of technology use is clearly seen as respondent agreed to the usage of at least one SWS device; with SWWs 171 (45.6%) been the most used wearable devices, followed closely by SWBs 130 (34.7%). On the other hand, the SRs and STs seems to be unpopular and least desired with 34 (9.1%) and 40 (10.7%) respectively. In terms of the utility of SWSs, the majority of the respondents (58.4%) reported that, these wearable sensors are not only useful in keeping track of their physical health, but also motivate them to better understand their healthcare needs. While 49.1% of the respondents believed that indeed, wearable sensors enhances the communication between them and their doctors, a lesser percentage of the respondents (36.3%) are of the opinion that wearable sensors does not in any way reduce the cost of healthcare since the actual cost of health care is borne by the users. On the contrary, some of the respondents, finds wearable sensors not to be useful and of no effect (Table 2). According to the 375 respondents, among the wearable sensors examined, SWBs has the most significant positive impact in HHF and healthcare communications, SWWs also had a significant impact on HHF with 168 (44.8%) responders and 159 (44.2%) of inclinations respectively; these were trailed by the SRs and STs with 106 (28.3%) and 82 (21.9%) accordingly. However, some respondents opined that these wearable devices are associated with some negative influences while others are of no effect whatsoever (Table 3). As common with every technology, respondents who participated in the survey reported some issues associated with their use of SWSs and devices. Among these issues is personal motivation: for instance, anxieties related to technical know-how, and unavailability of a smart phone along with associated devices; re-affirming the study of Mosconi et al., (2019), closely trailed by inadequate prove to substantiate their accuracy and consistency, usefulness of data as well as technical obstacles. Surprisingly, low trust in confidentiality and privacy of data which is envisaged to greatly hinder the adoption and utilization of SWSs turned out to have the least concern with only 90 (24.0%) of the respondents affected. A small portion of respondents seems not to have any idea concerning the issues associated with SWSs and devices as can be seen in the table 4. This study on SWSs examined users' perspectives on the technological impact of SWSs in HHF. Findings from the study indicate that, among the SWS devices examined, SWWs appears to be the most commonly used wearable sensor device; providing access to healthcare information such as: physical activities, diet and weight management etc. followed by SWBs. Findings from the study is related to a recent survey on wearable health apps and wearable devices, where the most used healthcare apps were reported to be informative apps (Mosconi et al., 2019). In addition, this study is in contrast to those reported by (Wen et al., 2017) where bracelet-type wearable devices seems to be mostly preferred. Respondents are optimistic about the future benefits of SWSs in HHF; however, there seems to be a gap between personal motivation to use SWSs and trust in the confidentiality and privacy of data. There is therefore a need to further enlighten users on the importance of continuous usage. More indication needs to be provided to substantiate the effectiveness of the devices since they are not even worried about the confidentiality of data. Concerning the accuracy and reliability of data, users seem not to be bothered about the data generated by these devices; this is very significant since the lack of this might hinder the adoption of wearable sensors and devices (BinDhim and Trevena, 2015). Nevertheless, designers must endeavor to design products bearing in mind, ease of use and easy interpretation of data is key to its acceptance and continuous usage. It is also crucial, complete product design trials are carried out on people to determine the actual needs of users and the accuracy of data generated. Studies (Covolo et al., 2017;Mosconi et al., 2019) has shown that these trials are limited due to some managerial constraints. The study has some limitations. In the first instance, the response rate 94.22% (375/398) may be too small for this kind of study as such, may not be adequate for generalization. Secondly, the respondents are all members of a particular gym center. It is likely that their point of view differs from those in other gym centers. Hence, it is necessary for a further study which will cover a wider inclusion of various types of users.
Conclusion: Varieties of SWSs abound; resulting in user's difficulty to determine the ideal SWSs device suitable to meet their healthcare needs. This study, which examined the technological impact of wearable sensors enhance the body of knowledge by identifying which of these devices user's find appealing and comfortable to use. Evidently there are issues associated with the use of SWSs; it is, however, expected that these issues be given the highest precedence to ensure a hitch free experience while using SWSs and devices.