Decoherence in quantum walks – a review

May combine two claims.

Both continuous-time and discrete-time quantum walks on the line spread linearly, with different constant prefactors, and both show a quadratic speedup in spreading compared with classical random walks.

“Both spread linearly, but with different constant prefactors, so both show a quadratic speed up in their spreading compared to classical random walks.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For a continuous-time quantum walk on the line with hopping rate γ = 0.5, after 40 time units the probability distribution is as shown in Figure 2.

“Using a hopping rate of γ = 0.5 so that the total hopping probability per unit time is one, after 40 units of time we get the probability distribution shown in Figure 2.”

May combine two claims.

The continuous-time and discrete-time quantum walks on the line propagate at somewhat different speeds, as evidenced by the different time instants at which they have the same width.

“The two types of walks propagate at somewhat different speeds, as evidenced by the different time instants at which they have the same width.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The continuous-time quantum walk on the line is always symmetric if the hopping rate is the same in both directions.

“The continuous-time quantum walk on the line is always symmetric if the hopping rate is the same for both directions”

Probably not a substantial claim: may not pass S3 (load-bearing).

Equation (28) has a straightforward solution expressed in terms of Bessel functions.

“Equation ( 28) has a straightforward solution in terms of Bessel functions,”

Probably not a substantial claim: may not pass S3 (load-bearing).

The continuous-time quantum walk on the line has a very oscillatory nature, especially in the central region.

“Nonetheless, the continuous-time walk has a very oscillatory nature, especially in the central region.”

May combine two claims.

θ measures the strength of dephasing, with θ = π/4 being complete dephasing (classical walk) and θ = 0 being a pure quantum walk; the approximation is not valid for exactly θ = 0.

“where θ measures the strength of the dephasing, with θ = π/4 being complete dephasing (classical walk) and θ = 0 being a pure quantum walk (the approximation above is not valid for exactly θ = 0).”

May combine two claims.

Decoherence on the coin only does not produce a top-hat distribution; instead the distribution develops a cusp as it passes from quantum to classical.

“Decoherence on the coin only does not produce a top-hat distribution, instead the distribution develops a cusp as it passes from quantum to classical.”

May combine two claims.

The bounding procedure is reasonably accurate; numerical studies give the coefficient of p in the expansion as 0.09566, compared with the bound of 0.20711.

“The bounding procedure applied here is reasonably accurate -numerical studies give the coefficient of p in the above expansion as 0.09566, compared with the bound of 0.20711.”

May combine two claims.

The optimum decoherence rate depends on the number of steps in the walk: p_u T ≈ 2.6 for decoherence on both coin and position and p_u T ≈ 5 for decoherence on the position only.

“The optimum decoherence rate depends on the number of steps in the walk: p u T 2.6 for decoherence on both coin and position and p u T 5 for decoherence on the position only (obtained numerically in Kendon and Tregenna (2003)).”

• cites Kendon and Tregenna (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

For small q and large T, the variance σ2(T,q) is approximately T(1+q^4), and the standard deviation is approximately √T √(1+q^4/2) to lowest order in q.

“From the continued expansion of equation ( 72), the prefactor is q 4 (1q) T -4 , so for small q and large T , we have σ 2 (T , q) T (1 + q 4 ), and for the standard deviation σ(T , q) √ T 1 + q 4 2 (77 ) to lowest order in q ≡ 1p.”

May combine two claims.

The slope of σ(T,p) is finite as p→0 and zero at p=1.

“The slope of σ(T , p) is finite as p → 0 and zero at p = 1.”

May combine two claims.

Dür et al.'s numerical work shows that imperfect shifts or spontaneous tunnelling smear the distribution without necessarily reducing quantum features.

“Their work is numerical, but shows that imperfect shifts, or spontaneous tunnelling, smear out the distribution without necessarily reducing the quantum features.”

• cites Dür et al. (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

Ryan et al. artificially applied decoherence to the qubits and observed that the quantum walk degrades into the classical walk.

“Ryan et al. also applied decoherence artificially to the qubits to observe that the quantum walk degrades into the classical walk.”

• cites Ryan et al. 2005Not checked yet

  Not checked in the free run.

May combine two claims.

There are several ways to make photons follow quantum walk dynamics; some have been implemented, but all implementations used high light intensities that admit a classical wave description.

“There are a number of ways in which photons can be made to follow a quantum walk dynamics, and while some have been implemented, all have used high light intensities that admit a classical wave description.”

Probably not a substantial claim: may not pass S2 (checkable). May combine two claims.

There are many gaps in the analysis of decoherence in quantum walks and in understanding what makes a useful quantum walk algorithm.

“there are many gaps in the analysis of decoherence in quantum walks, and, more importantly, many gaps in our understanding of what might make a useful quantum walk algorithm.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.

No study of decoherence in quantum walks on directed graphs has been done, nor has the class of graphs that could be the pattern of a CP map been considered.

“For example, no study of decoherence in quantum walks on directed graphs has been done, nor consideration of the class of graphs that might be the pattern of a CP map (rather than of a unitary matrix).”

May combine two claims.

The continuous-time walk does not produce as nice a top-hat as the discrete-time walk, partly due to support on all sites rather than alternate sites.

“The continuous-time walk does not produce quite such a nice top-hat as the discrete-time walk, partly due to having support on all sites rather than alternate sites, though it would probably be equally useful in practice.”

Classified as probably not a substantial claim.

Many examples studied so far are exceptional cases, because a slight change in symmetry of dynamics or initial state can reverse the interesting quantum properties.

“Many of the examples studied so far turn out on closer inspection to be exceptional cases, in that a slight change in the symmetry of the dynamics or initial state can reverse the interesting quantum properties.”

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

No published analytical treatments exist for decoherence in a continuous-time quantum walk on a line.

“In contrast to the extensive studies of the discrete-time walk on the line, there are no published analytical treatments of decoherence in a continuous-time quantum walk on the line.”

May combine two claims.

In the continuous-time model, p can be made arbitrarily large; at p=8000 the walk hardly leaves the starting point.

“there is no reason why p in equations ( 85) and ( 86) cannot be made arbitrarily large.In Figure 11, p = 8000 is shown: the walk hardly manages to leave the starting point.”

May combine two claims.

The optimal decoherence rate removes all quantum entanglement, which can be seen as removing extra quantum correlations that keep the distribution away from uniform.

“The optimal decoherence rate turns out just to remove all the quantum entanglement, and can be thought of as removing the 'extra' quantum correlations that would otherwise keep the distribution away from uniform.”

• cites Kendon and Maloyer (2006)Not checked yet

  Not checked in the free run.

May combine two claims.

The time-averaged probability distribution of the continuous-time quantum walk on a cycle mixes asymptotically in general, but its limiting distribution is not uniform and retains one or more peaks reflecting the initial state.

“While this does mix asymptotically, in general, like the discretetime walk, the limiting distribution is not uniform: it retains one or more peaks reflecting the initial state.”

May combine two claims.

The quantum walk on a line spreads much faster than the classical random walk, producing a spiky distribution that is a discrete form of an Airy function.

“The quantum walk looks nothing like the classical random walk, it spreads out much faster in a spiky distribution that is a discrete form of an Airey function (Carteret et al. 2003).”

• cites Carteret et al. 2003Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

In the graph-based description, the stochastic matrix of a Markov chain corresponds to the adjacency matrix.

“The stochastic matrix governing the Markov chain corresponds to the adjacency matrix in the graph-based description above.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Quantum walks have been used as the clock mechanism in a Feynman computer.

“They have also found applications from the early days of quantum computation as the clock mechanism in a Feynman computer (Feynman 1986).”

• cites Feynman 1986Not checked yet

  Not checked in the free run.

Classified as probably not a substantial claim. May combine two claims.

Quantum walks are simple systems in which decoherence can be studied analytically and numerically, connecting to areas such as quantum chaos.

“Quantum walks are simple systems in which the intricacies of decoherence can be studied both analytically and numerically, making connections with fields such as quantum chaos.”

May combine two claims.

Aharonov et al. proved that the coined quantum walk on an odd cycle mixes to the uniform distribution, with mixing time bounded above by O(ε^{-3} N log N), almost quadratically faster than a classical random walk.

“Aharonov et al. (2001) proved that the coined quantum walk on a cycle with an odd number of nodes does mix to the uniform distribution, and has M( ) bounded above by O( -3 N log N), which is almost quadratically faster (in N) than a classical random walk.”

• cites Aharonov et al. (2001)Not checked yet

  Not checked in the free run.

May combine two claims.

The quantum walk on a line is asymmetric, and the asymmetry is determined by the initial coin state.

“It is also asymmetric, with the asymmetry determined by the initial coin state.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For a classical random walk on a line, the standard deviation of the position after T steps is the square root of T.

“The standard deviation of P (x, T ) is √ T , that is, the walker is found on average √ T steps from the origin after T steps of the random walk.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Classical random walks on a cycle mix to a uniform distribution in O(N2) time.

“Classical random walks on a cycle mix to a uniform distribution in a time O(N 2 ).”

May combine two claims.

Time-averaging makes the quantum mixing time depend on 1/ε, whereas the classical mixing time depends on log(1/ε).

“the scaling of the mixing time M( ) depends on 1/ , compared to log(1/ ) for a classical random walk”

May combine two claims.

The standard deviation of the quantum walk on a line is linear in T, unlike the square-root-T behaviour of the classical walk.

“The standard deviation (from the origin) σ(T ) is thus linear in T , in contrast to √ T for the classical walk.”

Probably not a substantial claim: may not pass S4 (based).

In classical random walks, the properties of the limiting distribution depend only on the form of the graph.

“In classical random walks, the properties of the limiting distribution depend solely on the form of the graph.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The simple quantum walk on a line has been thoroughly studied.

“the simple quantum walk on a line has now been thoroughly studied”

• cites Ambainis et al. (2001)Not checked yet

  Not checked in the free run.

• cites Bach et al. (2004)Not checked yet

  Not checked in the free run.

• cites Yamasaki et al. (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

Exact instantaneous mixing for continuous-time quantum walks on cycles is known only for N = 3 and N = 4, fewer cases than are known for discrete-time walks on cycles.

“is known to have exact instantaneous mixing for only a few special cases, N = 3 and N = 4 (Ahmadi et al. 2003), that is, even fewer cases than are known for the discrete-time walk on the cycle as mentioned in Section 2.3.”

• cites Ahmadi et al. 2003Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

For a classical random walk on a line, the position distribution after T steps is binomial.

“If the random walk is repeated many times, the probability distribution P (x, T ) obtained is binomial, as is well known and easily shown.”

May combine two claims.

Hadamard walks on odd cycles converge to the uniform distribution, while those on even cycles converge to a non-uniform distribution unless an extra phase δ is added to the coin.

“Hadamard walks on cycles with an odd number of nodes converge to the uniform distribution (as was proved in Aharonov et al. (2001)), but those with an even number converge to a non-uniform distribution unless an extra phase δ is added to the Hadamard coin operator”

• cites Aharonov et al. (2001)Not checked yet

  Not checked in the free run.

• cites Tregenna et al. (2003)Not checked yet

  Not checked in the free run.

• cites Bednarska et al. (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

Quantum random walks on cycles are deterministic, oscillate forever, and generally do not mix even instantaneously.

“quantum random walks are deterministic, they oscillate forever, and, in general, do not mix even instantaneously.”

Classified as probably not a substantial claim.

Quantum algorithms that use quantum walks follow unitary evolution except for the final measurement.

“These all follow a unitary quantum evolution, apart from the final measurement.”

May combine two claims.

The adjacency matrix of the N-vertex cycle graph is circulant, with eigenvalues λ_x = 2 cos(2πx/N) and corresponding eigenvectors |b_x.

“The adjacency matrix A of the N-vertex cycle graph is a circulant matrix, it has eigenvalues λ x = 2 cos(2πx/N) with corresponding eigenvectors |b x”

Classified as probably not a substantial claim. May combine two claims.

There are many similarities between discrete and continuous-time quantum walks, but also distinctly different behaviours, and this remains true under decoherence.

“As we have seen, while there are many similarities between discrete and continuous-time quantum walks, there are also some distinctly different behaviours, and this turns out to be true also under the influence of decoherence.”

Probably not a substantial claim: may not pass S3 (load-bearing).

One of the earliest uses of non-unitary quantum walks, in Aharonov et al. (1992), was measurement-based.

“One of the earliest uses of non-unitary quantum walks, in Aharonov et al. (1992), was measurement-based.”

• cites Aharonov et al. (1992)Not checked yet

  Not checked in the free run.

May combine two claims.

Spatial searching, where moving between database items is counted as a cost, is faster with a quantum algorithm, and the continuous-time walk finds it a little harder than the discrete-time walk: in low dimensions it needs a coin too.

“Spatial searching, where moving from one item in the database to the next is also counted as a cost, is also faster with a quantum algorithm, and, curiously, the continuous-time walk finds this a little harder than the discrete-time walk: in low dimensions it needs a coin too (Childs and Goldstone (2004a;2004b).”

• cites Childs and Goldstone (2004a;2004b)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Classical random walks underpin many standard methods in computational physics, such as Monte Carlo simulations.

“Classical random walks also underpin many standard methods in computational physics, such as Monte Carlo simulations.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Carlson et al. identified a class of graphs that are instantaneous uniform mixing, namely claw or star graphs.

“Carlson et al. also identified another class of graphs that are instantaneous uniform mixing -the claw or star graphs.”

• cites Carlson et al.Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The discrete-time quantum walk on the hypercube has approximate instantaneous mixing rather than exact mixing, and M(ε) mixing in exponential time.

“These results can be compared with the discrete-time walk on the hypercube, which has approximate instantaneous mixing (instead of exact), and M( ) mixing in exponential time.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Kendon and Tregenna (2003) evolved equation (49) numerically for various choices of P_j: projection onto position space; projection into coin space in the preferred basis |±1; and projection of both coin and position.

“Kendon and Tregenna (2003) took equation ( 49) and evolved it numerically for various choices of P j : projection onto the position space; projection into the coin space in the preferred basis | ± 1 ; and projection of both coin and position.”

• cites Kendon and Tregenna (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

The continuous-time quantum walk on the hypercube hits the opposite corner in linear time, exponentially faster than a classical random walk.

“The continuous-time quantum walk on the hypercube also hits the opposite corner in linear time, which is exponentially faster than a classical random walk”

Probably not a substantial claim: may not pass S3 (load-bearing).

Several variations on quantum searching for a single item have been analysed, all essentially searching for a set of marked items.

“Since then, several variations on quantum searching for a single item have been analysed, all essentially searching for a set of marked items of some sort (Magniez et al. 2005;Childs and Eisenberg 2005;Ambainis 2004).”

• cites Magniez et al. 2005Not checked yet

  Not checked in the free run.

• cites Childs and Eisenberg 2005Not checked yet

  Not checked in the free run.

• cites Ambainis 2004Not checked yet

  Not checked in the free run.

May combine two claims.

Adamczak et al. extended mixing analysis to a wider variety of circulant graphs, continued by Lo et al. (2006), and found that mixing to non-uniform distributions is the norm for these graphs.

“Adamczak et al. extended their analysis of mixing in continuous-time quantum walks to a wider variety of circulant graphs, this was continued in Lo et al. (2006): mixing to non-uniform distributions turns out to be the norm for these types of graphs.”

• cites Lo et al. (2006)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Keating et al. (2006), applying localisation theory (Anderson 1958), argued that this behaviour is exceptional and that on less regular graphs the norm is a quantum walk that tends to stay near its starting state.

“Keating et al. (2006) applied results from localisation theory (Anderson 1958) to argue that this behaviour is exceptional, and the norm on less regular graphs is a quantum walk that tends to stay near its starting state.”

• cites Keating et al. (2006)Not checked yet

  Not checked in the free run.

• cites Anderson 1958Not checked yet

  Not checked in the free run.

May combine two claims.

A quantum search of an unsorted database needs only O(√N) queries, though the queries ask for many answers in superposition.

“A quantum search only needs to make O( √ N) queries, though the queries ask for many answers in superposition.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The first proper algorithms using quantum walks appeared in Childs et al. (2003) and Shenvi et al. (2003), and more have followed.

“The first proper algorithms using quantum walks appeared in Childs et al. (2003) and Shenvi et al. (2003), and more have followed since: for a short survey, see Ambainis (2003).”

• cites Childs et al. (2003)Not checked yet

  Not checked in the free run.

• cites Shenvi et al. (2003)Not checked yet

  Not checked in the free run.

• cites Ambainis (2003)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Randomised algorithms provide the best known algorithms for approximating the permanent of a matrix, finding satisfying assignments to Boolean expressions (kSAT with k > 2), estimating the volume of a convex body, and graph connectivity.

“Randomised algorithms are one such arena, providing the best known algorithms for approximating the permanent of a matrix (Jerrum et al. 2001), finding satisfying assignments to Boolean expressions (kSAT with k > 2) (Schöning 1999), estimating the volume of a convex body (Dyer et al. 1991), and graph connectivity (Motwani and Raghavan 1995).”

• cites Jerrum et al. 2001Not checked yet

  Not checked in the free run.

• cites Schöning 1999Not checked yet

  Not checked in the free run.

• cites Dyer et al. 1991Not checked yet

  Not checked in the free run.

May combine two claims.

Kendon and Sanders (2004) gave a more systematic treatment of the quantum-to-classical transition in a general quantum walk, emphasising the importance of demonstrating both wave and particle dynamics and of interpolating between them by varying decoherence.

“A more systematic treatment of the quantum to classical transition in a general quantum walk appears in Kendon and Sanders (2004), which emphasises the importance of (a) demonstrating that quantum walks exhibit both wave (pure quantum) and particle (decohered) dynamics, and (b), for a non-unitary quantum walk, being able to interpolate between these two modes of behaviour by turning the decohere”

• cites Kendon and Sanders (2004)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Expanding the repertoire of methods for quantum algorithms motivated the recent upsurge of interest in quantum walks.

“Expanding the repertoire of methods for quantum algorithms was the motivation behind the recent upsurge of interest in quantum walks.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Motivated by likely experimental errors, Kendon and Tregenna also modelled an imperfect Hadamard by applying a Gaussian spread of standard deviation √pπ/4 about the perfect value π/2.

“Motivated by the likely form of experimental errors, they also modelled an imperfect Hadamard by applying a Gaussian spread of standard deviation √ pπ/4 about the perfect value of π/2 implicit in equation ( 8”

• cites Kendon and Tregenna (2003)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Many quantum algorithms found so far belong to the same family and are based on Fourier transforms to identify a hidden subgroup.

“Starting with Shor's algorithm for factoring large numbers (Shor 1997), many of the quantum algorithms found so far belong to the same family, and are based on the use of Fourier transforms to identify a hidden subgroup (Lomont (2004) provides a recent review).”

• cites Shor 1997Not checked yet

  Not checked in the free run.

• cites Lomont (2004)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The hidden-subgroup Fourier method works well for Abelian groups, but extending it to non-Abelian groups, where problems such as graph isomorphism lie, is proving tricky.

“This works well (that is, can be exponentially better than known classical methods) for Abelian groups, but extending the method to non-Abelian groups, where some of the notorious hard problems, such as graph isomorphism, lie, is proving tricky.”

May combine two claims.

Discrete and continuous-time quantum walks give broadly similar results for algorithmic properties such as mixing times and hitting times when both are applied to the same problem, with the possible exception of spatial search, which requires a coin for maximum efficiency even in the continuous-time walk in low dimensions.

“They give broadly similar results for algorithmic properties such as mixing times and hitting times in those cases where both forms have been applied to the same problem, with the possible exception of spatial search (Childs and Goldstone 2004a), which, as noted above, requires a coin for maximum efficiency even in the continuoustime walk in low dimensions (Childs and Goldstone 2004b).”

• cites Childs and Goldstone 2004aNot checked yet

  Not checked in the free run.

• cites Childs and Goldstone 2004bNot checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

A quadratic speedup is the best possible improvement for unsorted database search.

“It can be shown that a quadratic speed up is the best possible improvement for this problem (Bennett et al. 1997).”

• cites Bennett et al. 1997Not checked yet

  Not checked in the free run.

May combine two claims.

Moore and Russell (2002) gave an analytical solution for continuous-time quantum walks on the hypercube as well as for the discrete-time walk.

“Moore and Russell (2002) gave an analytical solution for the continuous-time quantum walks on the hypercube as well as for the discrete-time walk (see Section 2.4).”

• cites Moore and Russell (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

Košík et al. showed that the resulting distributions match the expected classical random walks, which may be biased if the initial state or coin operator is biased.

“They show that the resulting distributions match the expected classical random walks (which may be biased if the initial state or coin operator is biased,”

• cites Košík et al. (2006)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The first quantum algorithm for unsorted database search was Grover (1996), using amplitude amplification, giving a quadratic speedup over classical searching.

“The first quantum algorithm for this problem was given in Grover (1996), using a method of amplitude amplification, from which a quadratic speed up over classical searching is obtained.”

• cites Grover (1996)Not checked yet

  Not checked in the free run.

May combine two claims.

With γ = 1/n, the continuous-time quantum walk on the hypercube mixes exactly instantaneously in time O(n), a logarithmic improvement over O(n log n) for the mixing time of a classical random walk.

“With this choice, the continuous-time quantum walk mixes exactly instantaneously in time O(n), which is a logarithmic improvement over O(n log n) for the mixing time of a classical random walk.”

• cites Moore and Russell (2002)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The proof for the glued-trees algorithm is technical, involving oracles and consistent colourings, and requires simulation of a continuous-time quantum walk on a discrete quantum computer.

“The proof is quite technical, involving oracles and consistent colourings of the network, and requires the simulation of a continuous-time quantum walk on a discrete quantum computer.”

• cites Childs et al. (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

The converse does not apply: because position is conditioned on the coin state, decohering the position also decoheres the coin.

“The converse does not apply, because the position is conditioned on the state of the coin, equation (2), thus decohering the position decohers the coin with it.”

May combine two claims.

Decoherence causes the quantum walk to mix to the uniform distribution without any averaging of P(x,T,p), thus retaining the logarithmic scaling with ε for the mixing times; this is effective enough to be useful for decoherence on the position.

“However, one can do better than this: decoherence causes the quantum walk to mix to the uniform distribution without any averaging of P (x, T , p), thus retaining the logarithmic scaling with for the mixing times.It is obvious that decoherence must do this, since high decoherence rates reproduce the classical random walk, which has this property.The only question is whether it does so effectively”

• cites Kendon and Maloyer 2007Not checked yet

  Not checked in the free run.

• cites Richter 2007bNot checked yet

  Not checked in the free run.

May combine two claims.

When the time-averaged distribution is considered, mixing to the uniform distribution occurs for some coin operators, but at the cost of requiring a number of steps linear in the inverse accuracy 1/ε instead of logarithmic, unless repetitions are combined in an amplification procedure.

“In that case, mixing to the uniform distribution M( ), equation ( 15), does occur for some choices of coin operator, but this comes at the cost of requiring a number of steps linear in the inverse accuracy 1/ instead of logarithmic, unless a number of repetitions are combined in an amplification procedure.”

May combine two claims.

Since decohering the position also decoheres the coin, it makes only a small difference whether the coin is also decohered explicitly.

“Since, as already explained, decohering the position also decoheres V. Kendon 1194 the coin, it makes only a small difference whether or not we also decohere the coin explicitly.”

May combine two claims.

In Lopéz and Paz's study, the dynamics are restricted to cycles, but most results are for small numbers of time steps such that the walk has not joined up round the cycle, and the results are identical to the walk on the line.

“In their study, Lopéz and Paz restrict the dynamics to cycles.However, most of their results are for small numbers of time steps such that the walk has not joined up round the cycle, and the results are identical to the walk on the line.”

• cites Lopéz and Paz (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

Brun et al. (2003c) considered multiple coins used in sequence, repeating after all coins had been used once; this produces a quantum walk that still spreads linearly with the number of steps, but with the rate of spreading reduced inversely by the number of coins.

“The first such study, Brun et al. (2003c), considered multiple coins used in sequence, with the sequence repeating after all the coins had been used once.This produces a quantum walk that still spreads linearly with the number of steps, but with the rate of spreading reduced inversely by the number of coins.”

• cites Brun et al. (2003c)Not checked yet

  Not checked in the free run.

May combine two claims.

While decohering the coin state is sufficient to reduce a quantum walk on a cycle to a classical walk, if the walker started in a superposition of two position states, this remains untouched by the decoherence.

“This brings out beautifully the fact that while decohering the coin state is sufficient to reduce a quantum walk on a cycle to a classical walk, if the walker started in a superposition of two position states, this remains untouched by the decoherence.”

• cites Lopéz and Paz (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

For all types of decoherence, the odd-N cycle shows a minimum mixing time at a decoherence rate somewhat earlier than the even-N cycle, roughly p = 2/N^2, but because of the oscillatory nature of P(x,T,p), the exact behaviour is not a smooth function of p or ε.

“For all types of decoherence, the odd-N cycle shows a minimum mixing time at a decoherence rate somewhat earlier than the even-N cycle, roughly p = 2/N 2 , but because of the oscillatory nature of P (x, T , p), the exact behaviour is not a smooth function of p or .”

• cites Kendon and Tregenna 2003Not checked yet

  Not checked in the free run.

May combine two claims.

As decoherence on the position (or both coin and position) increases, the oscillations in P(x,T,p) are damped out; at p ≈ 16/N^2 the mixing time passes smoothly through an inflexion and then behaves quantitatively similarly to adjacent-sized even-N cycles, including scaling as M_min(ε,p)=O(N/ε) at the inflexion. Thus for 0 < p ≲ 16/N^2 there is a region where the mixing time stays linear in N.

“As decoherence on the position (or both coin and position) increases, the oscillations in P (x, T , p) are damped out.At p 16/N 2 , the mixing time passes smoothly through an inflexion, and from then on behaves in a quantitatively similar manner to the adjacent-sized even-N cycles, including scaling as M min ( , p) = O(N/ ) at the inflexion.Thus for 0 < p .16/N 2 there is a region where the mixing”

• cites Kendon and Tregenna 2003Not checked yet

  Not checked in the free run.

May combine two claims.

Decoherence on the position produces a minimum mixing time M_min(ε,p) = O(N/ε), so the even-N cycle mixes to uniform in linear time for a suitable decoherence rate p_min ∼ 16/N^2, independent of ε.

“Decoherence on the position produces a minimum mixing time M min ( , p) = O(N/ ), thus the even-N cycle mixes to uniform in linear time for a suitable choice of decoherence rate p min ∼ 16/N 2 , independent of .”

• cites Kendon and Tregenna 2003Not checked yet

  Not checked in the free run.

May combine two claims.

Even a small amount of decoherence makes the quantum walk classical in the sense that the standard deviation of position scales as √t, but with a larger prefactor the smaller the dephasing; cot2 2θ ∼ 1/θ2 for small θ.

“This shows that even a small amount of decoherence renders the quantum walk classical in the sense that the standard deviation of the position scales as √ t, but with a larger prefactor the smaller the dephasing: cot 2 2θ ∼ 1/θ 2 for small θ.”

May combine two claims.

In that link-breaking model, for low rates of link-breaking the quantum behaviour persists, while for high rates the walk makes less progress than an unimpeded classical random walk.

“For low rates of link-breaking, the quantum behaviour persists, while for high rates the walk makes less progress than even an unimpeded classical random walk.”

• cites Romanelli et al. (2004)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Krovi and Brun's numerical results suggest that Kempe's bound H_concurrent(Ω(1)) ≤ O(n^2 log n^2) is not tight, and the actual hitting time seems better in the large-n limit.

“Their numerical results suggest the bound of H concurrent (Ω(1)) 6 O(n 2 log n 2 ) obtained by Kempe (2003b;2005) is not tight, the actual hitting time seems to be better than this in the large-n limit.”

• cites Krovi and Brun 2006aNot checked yet

  Not checked in the free run.

• cites Kempe 2003b;2005Not checked yet

  Not checked in the free run.

May combine two claims.

For odd-N cycles with no decoherence, Kendon and Tregenna reported M(ε) ∼ N/ε, compared to the upper bound M(ε) ∼ N log N/ε^3 given in Aharonov et al. (2001); Richter (2007b) confirmed this analytically.

“For odd-N cycles with no decoherence, they reported that M( ) ∼ N/ as compared to the upper bound of M( ) ∼ N log N/ 3 given in Aharonov et al. (2001).Richter has recently confirmed this analytically (Richter 2007b).”

• cites Aharonov et al. (2001)Not checked yet

  Not checked in the free run.

• cites Richter 2007bNot checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Brun et al. chose pure dephasing for the decoherence on the coin, with coin projectors P±1 = ...

“Brun et al. (2003b) chose pure dephasing for the form of the decoherence on the coin, so the coin projectors in equation ( 55) are”

• cites Brun et al. (2003b)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

This calculation first appeared in Kendon and Tregenna (2002).

“This calculation first appeared in Kendon and Tregenna (2002).”

• cites Kendon and Tregenna (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

The decoherence rate at the minimum mixing time is approximately π/N for odd-sized cycles or 2π/N for even-sized cycles, and the mixing time itself scales as O(N log(1/ε)), providing a quadratic improvement over the classical mixing time O(N^2 log(1/ε)).

“The decoherence rate at the minimum mixing time is approximately π/N (odd-sized) or 2π/N (even-sized), and the mixing time itself scales as O(N log(1/ )).This thus provides a quadratic improvement over the classical mixing time, which scales as O(N 2 log(1/ )).”

• cites Kendon and Maloyer 2007Not checked yet

  Not checked in the free run.

• cites Richter 2007bNot checked yet

  Not checked in the free run.

May combine two claims.

For N divisible by 4, the coin-decohered mixing time shows a minimum below the classical value at p ≈ 2/N, but this mixing time is ≳ N^2/32, so it remains quadratic in N; thus coin noise causes even-N cycles to mix to uniform but does not produce a significant speed-up over the classical random walk.

“Although for N divisible by 4, the coin-decohered mixing time shows a minimum below the classical value at p 2/N, this mixing time is & N 2 /32 , that is, it is still quadratic in N. Thus, although noise on the coin causes the even-N cycle to mix to the uniform distribution, it does not produce a significant speed up over the classical random walk.”

• cites Kendon and Tregenna 2003Not checked yet

  Not checked in the free run.

May combine two claims.

Overall, as for the walk on a line, there is a useful window within which decoherence enhances rather than degrades the quantum features of the walk; decoherence is necessary to ensure efficient scaling with precision, and it ensures the quantum walk mixes to a uniform distribution regardless of initial conditions or choice of coin operator.

“The overall conclusion is thus the same as for the walk on a line: there is a useful window within which decoherence enhances rather than degrades the quantum features of the walk.Moreover, it is actually necessary to ensure that the scaling with precision is efficient.Additionally, decoherence ensures the quantum walk mixes to a uniform distribution, regardless of the initial conditions or choice”

May combine two claims.

Richter (2007b) proves that the optimal mixing time is O(N log(1/ε)) and that three different strategies for optimising the mixing time are equally effective.

“Richter (2007b) actually proves not only that the optimal mixing time is O(N log(1/ )), but also that three different strategies for optimising the mixing time are equally effective.”

• cites Richter 2007bNot checked yet

  Not checked in the free run.

May combine two claims.

These low-decoherence effects are not algorithmically significant, do not alter the scaling of quantum processing, but may be useful in practice and represent intriguing complex behaviours worthy of study.

“These effects are not algorithmically significant, that is, they do not alter the scaling of quantum processing, but, nevertheless, may be useful in practice, and represent intriguing and complex behaviours worthy of study in their own right.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Determining whether a directed graph admits a unitary dynamics respecting its structure is a hard problem with no known general answer.

“In contrast, determining whether a directed graph allows a unitary dynamics that respects the graph structure is a hard problem, to which a general answer is not known.”

May combine two claims.

The continuous-time quantum walk under continuous monitoring suffers a quantum Zeno effect, a phenomenon that does not appear in coined quantum walks; one consequence is that quantities such as the concurrent hitting time are infinite, since continuous monitoring ensures the walk never arrives.

“In other words, the walk suffers a quantum Zeno effect (Misra and Sudarshan 1977), a phenomenon that does not appear in coined quantum walks.One consequence of this is that quantities such as the concurrent hitting time are infinite, since the continuous monitoring will ensure the continuous-time quantum walk never arrives.”

• cites Misra and Sudarshan 1977Not checked yet

  Not checked in the free run.

May combine two claims.

When no decoherence is present, the walk hits at H_one-shot(1) = nπ(2c+1)/2k and does so exactly, r(c)=1; this corresponds to the discrete-time result in Kempe (2003b;2005), so both discrete-time and continuous-time quantum walks on the hypercube exhibit exponentially faster hitting times than classical random walks, with the difference that the continuous-time walk hits exactly while the discrete

“When no decoherence is present, the walk hits at H one-shot (1) = nπ(2c + 1) 2k , and it does so exactly, that is, r(c) = 1.This corresponds to the result for the discrete-time quantum walk given in Kempe (2003b;2005), see Section 5.6, so both discrete-time and continuous-time quantum walks on the hypercube exhibit exponentially faster hitting times than classical random walks.The difference is”

• cites Kempe (2003b;2005)Not checked yet

  Not checked in the free run.

May combine two claims.

With the decoherence model where projectors choose a vertex uniformly at random, each dimension of the hypercube behaves independently, and provided the initial state is decomposable, the evolution remains decomposable as a system of n non-interacting qubits.

“We now show that with the model of decoherence described above each dimension still behaves independently.Recall equation ( 41) showing that the adjacency matrix for the hypercube decomposes into a sum of tensor products, with each acting only on a single qubit.Since the noise operators P j also have this structure, provided ρ(0) starts off in a state that is also decomposable (such as the all”

• cites Alagić and Russell (2005)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Dür et al. proposed a quantum walk on a line using an atom hopping between traps in an optical lattice.

“Dür et al. (2002) proposed a quantum walk on the line using an atom hopping between traps in an optical lattice.”

• cites Dür et al. (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

Decoherence in discrete-time walks has provided a number of notable common features, such as smoother spreading, enhanced mixing, and a transition from under-damped (quantum) to over-damped (classical) behaviour, analogous to classical damping in a harmonic oscillator.

“Decoherence in discrete-time walks has thus provided us with a number of notable common features, such as smoother spreading, enhanced mixing, and a transition from under-damped (quantum) to over-damped (classical) behaviour, which is analogous to classical damping in a harmonic oscillator.”

May combine two claims.

The overview shows that continuous-time walks exhibit some of the same effects of enhanced mixing and smoother spreading, and that where decoherence does not directly help, the quantum speed-up is at least robust under small amounts of decoherence.

“We have observed some of the same effects of enhanced mixing and smoother spreading, and also shown that where the decoherence does not directly help, the quantum speed up is at least robust under small amounts of decoherence.”

May combine two claims.

Ryan et al.'s experiment is a quantum computation of a quantum walk because three qubits represent the vertex label and the coin.

“This is actually a quantum computation of a quantum walk, since the three qubits are used to represent the binary number labelling the vertex (two qubits), and the qubit coin.”

• cites Ryan et al. 2005Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Sanders et al. proposed a quantum walk using the phase of a cavity electromagnetic field as position and an atom as coin.

“Sanders et al. (2003) suggested a quantum walk using the phase of the electromagnetic field in a cavity as the position (so the walk is again on a cycle) with the role of the coin played by an atom”

• cites Sanders et al. (2003)Not checked yet

  Not checked in the free run.

May combine two claims.

The concurrent hitting time already includes a portion of decoherence, but there is still a range 0 < p ≲ 1/n within which the quantum speed-up is preserved; in both one-shot and concurrent cases, p ≈ 1/n is a critical damping rate, smoothing out the second peak.

“The concurrent hitting time already includes a portion of decoherence (no extra features are produced by the addition of unselective decoherence), but there is still a range of 0 < p .1/n within which the quantum speed up is preserved.Note that in both the one-shot and concurrent cases, p 1/n is a critical damping rate, smoothing out the second peak (shown at around 40 (≡ 3nπ/2) steps in Figure 10”

• cites Kendon and Tregenna 2003Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Starting from an undirected graph, Watrous's mapping constructs a directed graph by treating each undirected edge as a pair of directed edges.

“Starting with an undirected graph, a corresponding directed graph can be constructed by a mapping due to Watrous (2001), which is similar to the line graph definition above, except that each undirected edge is treated as a pair of directed edges.”

• cites Watrous (2001)Not checked yet

  Not checked in the free run.

May combine two claims.

As p → ∞, the walk suffers from the quantum Zeno effect; informally, the rate of decoherence is so large that the walk is continuously being reset to the initial wave function |0>^⊗n by measurement, and P[0] → 1 and P[1] → 0.

“As p → ∞, the walk suffers from the quantum Zeno effect.Informally, we can say that the rate of decoherence is so large that the walk is continuously being reset to the initial wave function |0 ⊗n by measurement.By inspection of equations (119), it is clear that P [0] → 1 and P [1] → 0 as p → ∞.”

• cites Alagić and Russell (2005)Not checked yet

  Not checked in the free run.

May combine two claims.

For small p (pN << 1), the formula M(ε) appears to scale as log(N), but the 1/p scaling ensures M(ε) ≳ N for the range of validity; thus decoherence causes the continuous-time quantum walk to mix, with dominant effect a scaling of 1/p and only weak logarithmic dependence on N and ε.

“On the face of it, M( ) appears to scale as log(N), which would imply an exponential speed up over classical mixing times of O(N 2 ).However, this formula is only valid for pN 1, so the 1/p scaling ensures that M( ) N for the range of validity of the result.What this result tells us is that decoherence causes the continuous-time quantum walk to mix, with the dominant effect a scaling of 1/p, and”

May combine two claims.

By examining local maxima of P[1], the walk has approximate instantaneous hitting times to the opposite corner at H_one-shot(r) = 2πn(2c+1)/√(16k^2 - p^2) for all c ∈ Z, c > 0; however, the probability r(p,c) of measuring an exact hit decays exponentially as r(p,c) = 1/2 + 1/2 exp(-pπ(2c+1)/√(16k^2 - p^2))^n.

“By examining the local maxima of P [1], we can determine that the walk has approximate instantaneous hitting times to the opposite corner (1, . . ., 1) at times H one-shot (r) = 2πn(2c + 1) 16k 2 -p 2(121) for all c ∈ Z, c > 0. However, the probability r(p, c) of measuring an exact hit decays exponentially: r(p, c) = 1 2 + 1 2 exp (-pπ(2c + 1)/ 16k 2 -p 2 ) n . (122 )”

• cites Alagić and Russell (2005)Not checked yet

  Not checked in the free run.

May combine two claims.

These bounds show that M(ε) is linearly proportional to p, quadratically dependent on N, and logarithmically dependent on ε; the change in scaling with p from reciprocal for small p to linear for large p suggests a minimum mixing time at some intermediate decoherence rate, which Fedichkin et al. confirmed numerically.

“These bounds show that M( ) is linearly proportional to the decoherence rate p, but is quadratically dependent on N, and logarithmically dependent on .The change in the form of the scaling with p from reciprocal for small p to linear for large p suggests there is a minimum mixing time at some intermediate decoherence rate.Fedichkin et al. (2006) confirmed this numerically: see Figure 12.”

• cites Fedichkin et al. (2006)Not checked yet

  Not checked in the free run.

May combine two claims.

The proofs in Richter (2007b) are sufficiently general that they apply equally to continuous-time and discrete-time walks, filling the gap between small and large decoherence rates and proving that continuous-time walks with O(log(1/ε)) decoherence or measurement events mix in time O(N log(1/ε)) on the cycle and the d-dimensional torus.

“In fact, the proofs in Richter (2007b) are sufficiently general that they apply equally to the continuous-time walk as to the discrete-time walk.This fills the gap between small and large decoherence rates, and proves that continuous-time walks, with O(log(1/ )) decoherence or measurement events, mix in time O(N log(1/ )) on the cycle (and the d-dimensional torus).”

• cites Richter 2007bNot checked yet

  Not checked in the free run.

May combine two claims.

Fedichkin et al. (2006) gives the scaling for mixing times for the continuous-time walk on the cycle for both small and large decoherence rates, and augments this with numerical studies showing a minimum mixing time for intermediate decoherence rates.

“Fedichkin et al. (2006) gives the scaling for mixing times for the walk on the cycle for both small and large decoherence rates.They augment this with numerical studies showing a minimum mixing time for intermediate decoherence rates.”

• cites Fedichkin et al. (2006)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Physical systems can be made to perform a quantum walk, and this process is of interest as an example of precise coherent control.

“physical systems can be made to perform a quantum walk, and this process is of interest in its own right as an example of precise coherent control.”

Probably not a substantial claim: may not pass S3 (load-bearing).

Travaglione and Milburn described a scheme for a coined quantum walk using trapped-ion vibration modes coupled to an internal state as the coin.

“Travaglione and Milburn (2002) described how a coined quantum walk can be performed using the vibration modes of the trapped ion coupled to an internal state of the ion as the quantum coin.”

• cites Travaglione and Milburn (2002)Not checked yet

  Not checked in the free run.

May combine two claims.

Krovi and Brun found that using a DFT coin can make the hitting time infinite for certain configurations, while a Grover coin with a small distortion of the hypercube lattice increases the hitting time somewhat but it remains less than the classical random walk hitting time.

“The DFT coin has the property that, for certain configurations, the hitting time becomes infinite, while a Grover coin with a small distortion of the hypercube lattice increases the hitting time somewhat, though it is still less than the classical random walk hitting time.”

• cites Krovi and Brun 2006aNot checked yet

  Not checked in the free run.

May combine two claims.

These mixing times scaling linearly with n represent a quantum improvement over the classical random walk mixing time of Θ(n log n), with the caveat that the classical mixing time is not instantaneous, so strictly speaking the comparison is not like with like.

“These mixing times scaling linearly with n represent a quantum improvement over the classical random walk mixing time of Θ(n log n), with the caveat that the classical mixing time is not instantaneous, so, strictly speaking, we are not comparing like with like, since in the V. Kendon 1212 quantum case one must sample at exactly the right moment in time.”

May combine two claims.

This smoothing is useful for the one-shot hitting time, raising r(t) in the trough to well above the classical value, so it is no longer necessary to know exactly when to measure.

“This is useful for the one-shot hitting time, raising r(t) in the trough to well above the classical value, so it is no longer necessary to know exactly when to measure.”

May combine two claims.

Although decoherence causes an exponential decrease in r(t), the hitting times are short (only ∼ nπ/2 steps), so p ≈ 1/n only lowers r(t) by a factor of 1/e; this is insignificant for algorithmic purposes and still exponentially better than classical.

“However, the hitting times are short, only ∼ nπ/2 steps, so p 1/n only lowers r(t) by a factor of 1/e.This is insignificant for algorithmic purposes, as it is only a factor of order unity and thus still exponentially better than classical.”

May combine two claims.

The periodic mixing times decay with p and disappear altogether when p > 4k, so the quantum advantage tails off before the critical damping point is reached; Richter (2007b) offers a weak bound of O(n^{3/2} log(1/ε)) for the mixing time at around the critical damping point, which is slower than classical.

“Note that these periodic mixing times decay with p and disappear altogether when p > 4k, so the quantum advantage tails off before the critical damping point is reached.Richter (2007b) offers a weak bound of O(n 3/2 log(1/ )) for the mixing time at around the critical damping point, which is slower than classical.”

• cites Richter 2007bNot checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing).

Further work by Krovi and Brun suggests that whether quantum walks show dramatically different properties (speed up or slow down) compared with classical random walks is highly dependent on the symmetry of the graph.

“Further work by Krovi and Brun on the question of whether and under what conditions quantum walks show dramatically different properties (speed up or slow down) compared with classical random walks suggests that it is highly dependent on the symmetry of the graph (Krovi and Brun 2006b).”

• cites Krovi and Brun 2006bNot checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

The situation is simpler for restricted graph types such as line graphs.

“The situation is simpler for some restricted types of graphs, such as line graphs.”

May combine two claims.

Because a quantum walk occupies a subspace of the full quantum system, many decoherence sources move the system outside that subspace, so the decohered dynamics is not a classical random walk.

“Since the quantum walk takes place in a subspace of the full quantum system, many of the potential sources of decoherence take the system outside of the subspace of the quantum walk, so the resulting decohered dynamics is not a classical random walk.”

Probably not a substantial claim: may not pass S3 (load-bearing).

From a quantum perspective, the randomness is entanglement with an environment inaccessible to the eavesdropper.

“From a quantum perspective, the randomness takes the form of entanglement with an environment that the eavesdropper does not have access to.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Because total entanglement is limited, this reduces the key's entanglement with the eavesdropper and thus the eavesdropper's information.

“Since the total amount of entanglement is limited, this reduces the entanglement of the key with the eavesdropper, and thus reduces the information available to the eavesdropper.”

• AssumptionRests on an assumption: The total amount of entanglement is limited.
• AssumptionRests on an assumption: The eavesdropper does not have access to the environment.

Probably not a substantial claim: may not pass S3 (load-bearing).

This security enhancement works for both classical and quantum keys.

“This works for both classical and quantum keys.”

Probably not a substantial claim: may not pass S3 (load-bearing).

For irreversible graphs, Montanaro suggests splitting into reversible subgraphs with unitary dynamics and using a non-unitary partial measurement to switch between subgraphs while preserving coherence within each.

“For irreversible graphs, Montanaro suggests splitting the graph into subgraphs that are reversible, on which the quantum walk dynamics can be unitary, combined with a non-unitary step (a partial measurement) to switch between subgraphs in an irreversible way that, nonetheless, preserves coherence within each reversible subgraph.”

• cites Montanaro (2007)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S4 (based). May combine two claims.

Decoherence acts as a memory eraser that eliminates dependence on the initial state while retaining interesting quantum properties.

“The role of decoherence as a 'memory eraser' to eliminate the dependence on the initial state, while still retaining the interesting quantum properties, is thus one of its most appealing features.”

Probably not a substantial claim: may not pass S3 (load-bearing).

The addition of classical randomness can enhance a useful algorithmic property in other settings, both quantum and classical.

“The idea that the addition of classical randomness can enhance a useful algorithmic property also occurs in other settings, both quantum and classical.”

May combine two claims.

In quantum walks, decoherence or randomness induces a more uniform distribution, such as a smoother top-hat distribution on the line and faster mixing on finite graphs.

“the common theme is that the decoherence or randomness induces a more uniform distribution, in this case in the form of a smoother 'top-hat' distribution in the walk on the line, and faster mixing times on finite graphs.”

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

Montanaro defines reversibility for a directed graph and proves it permits a unitary quantum walk where the coin selects between sets of cycles rather than paths from each vertex.

“Montanaro (2007) defines 'reversibility' for a directed graph, and proves this allows for a unitary quantum walk in which the coin selects between different sets of cycles in the graph, rather than different paths from each vertex.”

• cites Montanaro (2007)Not checked yet

  Not checked in the free run.

Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.

The added randomness reduces the final secret key size but reduces the eavesdropper's information even more.

“The added randomness reduces the final size of the secret key, but it reduces even more the information that the eavesdropper has.”

Probably not a substantial claim: may not pass S2 (checkable), S3 (load-bearing).

Some shortcomings will only be accessible to serious study when a larger quantum computer is available to test actual algorithms.

“Some of these shortcomings will only be accessible to serious study when (if) we have a larger (that is, larger than we can simulate classically) quantum computer available to test the performance of actual algorithms.”

Probably not a substantial claim: may not pass S3 (load-bearing).

In quantum key distribution, adding a small amount of randomness during privacy amplification increases the security of the secret key.

“An example from the field of quantum information may be found in Kraus et al. (2005) and Renner et al. (2005), where the security of a quantum secret key is increased by adding a small amount of randomness to the key during the privacy amplification stage of the protocol.”

• cites Kraus et al. (2005)Not checked yet

  Not checked in the free run.

• cites Renner et al. (2005)Not checked yet

  Not checked in the free run.