Bell inequalities for (Measurement Based Quantum) Computation Dan Browne Dept. of Physics and Astronomy University College London s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Quantum Foundations (Measurement- Based) Quantum Computation Sunday, 1 August 2010 Measurement-based quantum computation Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state • 2. Then measure qubits individually, in certain (adaptive) bases, and post-process outcomes. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation • is a model of universal quantum computation. • 1. Create a special multi-qubit entangled state • e.g. A cluster state • 2. Then measure qubits individually, in certain (adaptive) bases, and post-process outcomes. • Via a suitable choice of measurements, any quantum computation can be acheived. R. Raussendorf and H.J. Briegel, “A one-way quantum computer”, PRL 2000. Sunday, 1 August 2010 Measurement-based quantum computation Measure a sub-set of qubits Process measurement results Choose bases for next subset of measurements Computational Output Prepare entangled resource state e.g. cluster state Requires classical “side-computation” Sunday, 1 August 2010 Measurement-based quantum computation +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle is pre-set and differs for each measurement. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle is pre-set and differs for each measurement. • But bit-value is calculated on the fly - and set equal to the parity of a sub-set of previous measurement outcomes. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation • For a cluster state resource it suffices for side-computation to be linear. • Each measurement is of the form and meas. outcomes are relabelled • The angle is pre-set and differs for each measurement. • But bit-value is calculated on the fly - and set equal to the parity of a sub-set of previous measurement outcomes. • Final output bits are encoded in the parity of a sub-set of the measurement outcomes. +1→ 0 − 1→ 1 cos θj X + (−1)sj sin θj Y R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). θj sj sj ∈ {0, 1} mj ∈ {0, 1} Sunday, 1 August 2010 Measurement-based quantum computation Measure a sub-set of qubits Process measurement results Choose bases for next subset of measurements Computational Output Prepare entangled resource state e.g. cluster state Requires (linear / XOR) classical “side-computation” Sunday, 1 August 2010 Bell inequalities Sunday, 1 August 2010 Bell inequalities Sunday, 1 August 2010 Bell inequalities • Bell inequalities (BIs) express restrictions on the joint probability distributions for spatially separated measurements in local hidden variable (LHV) theories. Sunday, 1 August 2010 CHSH inequality Outcome: Setting: s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} • We focus on the parity of the outcomes and define: Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality Outcome: Setting: s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} • We focus on the parity of the outcomes and define: • and show that for correlations in any LHV theory: Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state, Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state, Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: • A (loophole-free) demonstration of a Bell Inequality violation would refute local hidden variable theories. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 Sunday, 1 August 2010 CHSH inequality • With entangled quantum state, Alice and Bob can violate this inequality, although not exceeding Tsirelson’s bound: • A (loophole-free) demonstration of a Bell Inequality violation would refute local hidden variable theories. • The maximal violation (stronger than QM) is achieved by the Popescu-Rohrlich (PR) Box, which acheives E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 √ 2 B. S. Tsirelson, Lett. Math. Phys. (1980). S. Popescu and D. Rohrlich, Found. Phys. (1994) E0,0 + E0,1 + E1,0 − E1,1 = 4 Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 1 4 s1,s2 p(m1 ⊕m2 = s1s2|s1s2) ≤ 34 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH inequality • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: • Thus we can phrase the CHSH inequality in terms of a game. E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 1 4 s1,s2 p(m1 ⊕m2 = s1s2|s1s2) ≤ 34 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Es1,s2 = p(m1 ⊕m2 = 0|s1, s2)− p(m1 ⊕m2 = 1|s1, s2) Sunday, 1 August 2010 CHSH game • Rules: • Alice, Bob are given independent bits s1, s2 from a uniform distribution. • They may not communicate during the game. • Aim: • They should each produce a bit m1, m2, such that • We call games where the desired data is encoded in the XOR of measurement outcomes XOR-games. m1 ⊕m2 = s1s2 m1 XOR m2 = s1 AND s2 Sunday, 1 August 2010 CHSH game 1 4 s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 CHSH game • CHSH inequalities bound the mean success probability of the game. 1 4 s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 CHSH game • CHSH inequalities bound the mean success probability of the game. • The GHZ paradox can also be related to a very similar game. 1 4 s1,s2 p(m1 +m2 = s1s2) ≤ 3 4 ≤ 2 + √ 2 4 ≈ 0.85 LHV Quantum PR Box= 1 Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ = |ψ X ⊗ Y ⊗ Y |ψ = |ψ Y ⊗X ⊗ Y |ψ = |ψ |ψ = |001+ |110 which also imply: Y ⊗ Y ⊗X|ψ = −|ψ Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ = |ψ X ⊗ Y ⊗ Y |ψ = |ψ Y ⊗X ⊗ Y |ψ = |ψ |ψ = |001+ |110 which also imply: Y ⊗ Y ⊗X|ψ = −|ψ Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 GHZ correlation (uniquely) satisfies: X ⊗X ⊗X|ψ = |ψ X ⊗ Y ⊗ Y |ψ = |ψ Y ⊗X ⊗ Y |ψ = |ψ |ψ = |001+ |110 which also imply: Y ⊗ Y ⊗X|ψ = −|ψ GHZ “Paradox”: No (non-contextual) real number assignment of X and Y can satisfy all of these. Correlations in outcomes of local measurements} N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 • A very clean way to express this correlation is to use the binary notation introduced above. • I.e. the correlations “win” an XOR-game, nearly identical to the CHSH game. GHZ “paradox” s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 J. Anders and D. E. Browne PRL (2009). s1 + s2 Sunday, 1 August 2010 Geometric approach to Bell inequalities Sunday, 1 August 2010 • Another useful representation of Bell inequalities is to form a vector from the conditional probabilities. • Each possible set of conditional probabilities is represented a point in a unit hypercube. p = p(0, 0) p(0, 1) p(1, 0) p(1, 1) Geometric interpretation of BIs 0,0,0,0 1,1,1,1 p(s1, s2) ≡ p(m1 ⊕m2 = 1|s1, s2) conditional probability space Sunday, 1 August 2010 We can thus classify the regions of conditional probability space (2-D Schematic). Bell inequalities define facets of polytope. Quantum region LHV region: “Bell polytope” PR Box Marcel Froissart: Nouvo Cimento (1981), B.S. Tsirelson, J. Sov. Math. (1987) Geometric interpretation of BIs Sunday, 1 August 2010 Convex polytopes • The convex hull of a set of vectors (vertices) in R^d. • Generalisation of polygons, polyhedra to higher d. • May be defined in terms of its vertices or its facets (as a set of inequalities defining half planes.) Facet Vertex Facet inequality Sunday, 1 August 2010 Geometric interpretation of BIs • The “Bell polytope” represents the region of conditional probabilities allowed in LHV theories. • It is a hyper-octahedron. The facets represent the CHSH inequalities (and normalisation conditions). Marcel Froissart: Nouvo Cimento (1981). Sunday, 1 August 2010 Many-party Bell inequalities Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. s1 s2 m1 m2 sn mn · · ·M = j mj Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. s1 s2 m1 m2 sn mn · · ·M = j mj Sunday, 1 August 2010 Many-party Bell-inequalities • Werner and Wolf (2001) generalised the CHSH setting to n-parties. • We still keep 2-settings, 2-outputs per meas and consider conditional probs for the XOR of all outputs. • W & W derived the full n-party Bell polytope - and found that, for any n, it is a hyper-octahedron in 2^n dimensions. s1 s2 m1 m2 sn mn · · ·M = j mj Sunday, 1 August 2010 Loopholes in Bell inequality Experiments Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. • However, Bell’s assumptions are strict. • Space-like separated measurements • Perfect detection efficiency • Measurement settings chosen at random (free-will). Sunday, 1 August 2010 Loopholes in Bell Inequality experiments • The beauty of Bell inequalities is that they are experimentally testable. • However, Bell’s assumptions are strict. • Space-like separated measurements • Perfect detection efficiency • Measurement settings chosen at random (free-will). • If these do not hold, then the BIs may not hold - there may be loopholes. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Allowed LHV correlations under Bell’s assumptions Loopholes make the LHV region larger. Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Allowed LHV correlations under Bell’s assumptions Loopholes make the LHV region larger. Allowed LHV correlations under actual experimental conditions Sunday, 1 August 2010 Bell inequalities vs Measurement-Based Quantum Computation Sunday, 1 August 2010 MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs • Both • Require (only) XOR side-processing to perform computational game or task. • This task is impossible (non-linear) with XOR gates alone (linear gates). vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 MBQC vs BIs • But • MBQC requires adaptive measurements, and thus measurements cannot be space-like separated. • Spatial separation is one of the most important assumptions in deriving the Bell inequalities. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 This talk • Main result: • We will derive an equivalent of the Bell polytope for MBQC. • I.e. Within LHV theories, which measurement-based computations can be achieved? • Main tool: • Polytopes over Boolean functions. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Boolean Functions Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as where j =1, ..., 2^(2^n). f = f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11) Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as where j =1, ..., 2^(2^n). f = f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11) • I.e. There 2^(2^n) Boolean functions. Sunday, 1 August 2010 Boolean functions • A Boolean function is a map from n-bits to a single bit. • Every such function can be represented by a 2n bit vector listing the outputs for each of the 2n inputs. • E.g. • It is convenient to enumerate the Boolean functions as where j =1, ..., 2^(2^n). f = f(0 . . . 00) f(0 . . . 01) f(0 . . . 10) ... f(1 . . . 11) • I.e. There 2^(2^n) Boolean functions. fj(s) Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring • In other words, any Boolean function can be expressed as a sequence of XOR (add mod 2) and AND (multiply) gates. s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Boolean functions • Every Boolean function may be expressed as a polynomial (modulo 2) (known as “algebraic normal form”). • E.g. if input is the bitstring • In other words, any Boolean function can be expressed as a sequence of XOR (add mod 2) and AND (multiply) gates. • The degree of the polynomial is a useful way of classifying Boolean functions. s = s1s2 . . . sn f(s) = a0 + a1s1 + a2s2 + · · · + a12s1s2 + · · · Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written ak ∈ {0, 1}l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written ak ∈ {0, 1}l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate where k =1, ..., 2^(n+1). ak ∈ {0, 1} lk(s) l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. ak ∈ {0, 1} lk(s) l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. • Linear functions are closed under composition. ak ∈ {0, 1} lk(s) l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written • There are thus 2^(n+1) such functions, which we shall enumerate where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. • Linear functions are closed under composition. • In contrast, by composing a quadratic gate (e.g. NAND) one can generate all Booleans. ak ∈ {0, 1} lk(s) l(s) = a0 + n j=1 ajsj Sunday, 1 August 2010 Stochastic Boolean maps • Consider a stochastic machine which, given input string s, outputs with probability . fj(s) λj s j fj(s) choice: prob: λj Sunday, 1 August 2010 Stochastic Boolean maps • Consider a stochastic machine which, given input string s, outputs with probability . • The probability that the output bit of the machine is 1, conditional upon the input s, is given by: fj(s) λj p(1|s) = j λjp(fj(s) = 1) j λj = 1 s j fj(s) choice: prob: λj Sunday, 1 August 2010 Stochastic Boolean maps Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: p(fj(s) = 1) = fj(s) Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: • and thus obtain p(fj(s) = 1) = fj(s) p(1|s) = j λjfj(s) Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: • and thus obtain • or equivalently p(fj(s) = 1) = fj(s) p(1|s) = j λjfj(s) p = j λj fj Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: • and thus obtain • or equivalently • This is a convex combination of real-space vectors and thus a polytope, we call it the Boolean polytope. p(fj(s) = 1) = fj(s) p(1|s) = j λjfj(s) p = j λj fj Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: • and thus obtain • or equivalently • This is a convex combination of real-space vectors and thus a polytope, we call it the Boolean polytope. • Geometrically, it is a unit 2^n d. hypercube. p(fj(s) = 1) = fj(s) p(1|s) = j λjfj(s) p = j λj fj Sunday, 1 August 2010 The Linear Polytope lj(s)s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: lj(s)s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: lj(s) p = 2n+1 j=1 λjlj s jchoice: prob: λj Sunday, 1 August 2010 The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: • We shall call this the (n-bit) linear polytope. lj(s) p = 2n+1 j=1 λjlj s jchoice: prob: λj Sunday, 1 August 2010 The linear polytope •We can classify the linear polytope using standard techniques. • It has 2^(n+1) vertices in a 2^n dimensional space. • Can show that it is a hyper-octahedron. Sunday, 1 August 2010 Bell inequalities for MBQC Sunday, 1 August 2010 Bell inequalities for MBQC • Let us ask a “Bell inequality” type question for MBQC: • Using the correlations from a LHV theory, within an MBQC setting what computations can we achieve? vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. • For our question to make sense we make the following key assumption: vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. • For our question to make sense we make the following key assumption: • Side-computation will be solely linear. vs s1 ∈ {0, 1} m1 ∈ {0, 1} s2 ∈ {0, 1} m2 ∈ {0, 1} Sunday, 1 August 2010 Bell inequalities for MBQC • To simplify further, let’s initially adopt the precise CHSH (Werner-Wolf) setup. • Spatially separated parties with independent inputs. • Output of computation encoded in the XOR of all outcome bits. s1 s2 m1 m2 sn mn · · · M = j mj Sunday, 1 August 2010 Bell inequalities for MBQC • What computations can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. M(s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. M(s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. • Randomness arises in LHV theories by random assignment of the hidden variables. M(s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • What computations can this setup perform? • LHV model may be stochastic and thus the computations may include stochastic maps - allowed computations will form a region of the Boolean polytope. • Randomness arises in LHV theories by random assignment of the hidden variables. • Hence, this region will be a convex polytope, whose vertices correspond to the deterministic computations. M(s) LHV? Sunday, 1 August 2010 Bell inequalities for MBQC • First let us consider a single box. • The most general deterministic relationships between output and input can be written: • I.e. there are only 4 1-bit to 1-bit functions. sj mj aj ∈ {0, 1} bj ∈ {0, 1}mj = aj + bjmj Sunday, 1 August 2010 Bell inequalities for MBQC • If we associates bit aj and bj with each box, the most general expression for the output XOR bit is s1 s2 m1 m2 sn mn · · · M = j mj = j aj + j bjsj M = a+ j bjsj M(s) Sunday, 1 August 2010 Bell inequalities for MBQC M(s) = a+ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see M(s) = a+ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, M(s) = a+ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. M(s) = a+ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. • Hence the full range of computations achievable by LHV correlations with XOR on the outcomes M(s) = a+ j bjsj Sunday, 1 August 2010 Bell inequalities for MBQC • We see • this is linear in s, • by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. • Hence the full range of computations achievable by LHV correlations with XOR on the outcomes • is the Linear Polytope. M(s) = a+ j bjsj Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? • Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). Sunday, 1 August 2010 The linear polytope vs the Werner Wolf polytope • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. • Are they the same polytope? • Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). • Our derivation is a computational reformulation of the traditional Bell inequalities. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. • We have failed to derive Bell inequalities relevant to standard MBQC since that utilises adaptive measurements. Sunday, 1 August 2010 Bell inequalities for MBQC • So is this a failure? • We have reproduced a 10-year old result. • We have failed to derive Bell inequalities relevant to standard MBQC since that utilises adaptive measurements. • However, sometimes new representations give new insights.... Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! • All known loopholes must be associated with some non-linear computation. Sunday, 1 August 2010 Loopholes and linearity • Our Bell polytope is the polytope of linear functions. • Recall that a “loophole” is any experimental imperfection which enlarges the LHV region. • Since the LHV region is the linear polytope, and since linear functions are closed under composition. • Introducing extra linear computation will never introduce a loophole! • All known loopholes must be associated with some non-linear computation. • This allows us to weaken our assumptions and derive the same Bell inequalities. Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! • Why does this not induce a loophole? s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! • Why does this not induce a loophole? • In an experiment, we simulate the dependency using post-selection. s1 s2 m1 m2 m3 m1 ⊕m2 ⊕m3 = s1s2 s1 + s2 Sunday, 1 August 2010 An example: GHZ • In an experimental test of GHZ, the third input is set at random. •We then post-select our data, and only keep data where . s1 s2 m1 m2 m3 r r = s1 + s2 Sunday, 1 August 2010 An example: GHZ • In an experimental test of GHZ, the third input is set at random. •We then post-select our data, and only keep data where . • Does this induce a detection loop-hole? No, it doesn’t... s1 s2 m1 m2 m3 r r = s1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • Consider a more general setting. Let us set all inputs to n measurements as n uniformly random bits. • Let s be the input bit-string (provided by a referee, say). • We can post-select data such that each rj is a linear function of the bits in s. m1 m2 mn · · · r1 r2 rn M = a+ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. M = a+ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. • M is linear in rj. The rj’s are linear in s. Hence M is linear in s. M = a+ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. • M is linear in rj. The rj’s are linear in s. Hence M is linear in s. • M remains inside the linear polytope and no loopholes are induced - the LHV region is no larger than before. M = a+ j bjrj Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. m1 m2 r1 r2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. m1 m2 r1 r2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj are linear in r, M will remain within the linear polytope! m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj are linear in r, M will remain within the linear polytope! • This allows us to simulate linearly adaptive measurements, m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Linear measurement post-selection • But we can go further. • By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. • Since mj are linear in r, M will remain within the linear polytope! • This allows us to simulate linearly adaptive measurements, • And the linear polytope will still describe all LHV correlations. m1 m2 s1 m1 + s2 Sunday, 1 August 2010 Computational Bell inequalities Sunday, 1 August 2010 Computational Bell Inequalities • We can use these observations to generalise the traditional Bell inequalities. Sunday, 1 August 2010 Computational Bell Inequalities • We can use these observations to generalise the traditional Bell inequalities. • A computational Bell inequality is a facet of the polytope of Boolean stochastic maps achieved in any LHV theory • On a random m-bit input string s • Given n 2-setting, 2-outcome space-like separated measurements • With post-selection of measurement settings which are a linear function of input data and other measurement outcomes (simulated linear adaptivity) • And arbitrary linear pre- and post-computation. Sunday, 1 August 2010 Computational Bell Inequalities • The “Computational Bell inequalities” are easy to characterise. • For n ≥ m they are facets of the m-bit linear polytope. • Setting n = m and forbidding post-selection, we recover the traditional definition of CHSH inequalities. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. • But in our new framework, we can also allow extra parties, and simulated linear adaptive measurement. From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. • Usually only non- adaptive measurements are considered. • But in our new framework, we can also allow extra parties, and simulated linear adaptive measurement. • Do these enlarge the quantum region? From LHV to Quantum Correlations [1] Known as Tsirelson - Landau - Masanes region. A bigger quantum set? Sunday, 1 August 2010 • Yes! • For a fixed n, • Allowing extra parties • Allowing linear post-selection (simulated adaptivity). • can increase the quantum region. From LHV to Quantum Correlations Sunday, 1 August 2010 • Yes! • For a fixed n, • Allowing extra parties • Allowing linear post-selection (simulated adaptivity). • can increase the quantum region. • This can provide a greater degree of violation of Bell Inequalities than in the standard setting. From LHV to Quantum Correlations Sunday, 1 August 2010 Quantum correlations with adaptive measurements • For example, if we limit the number of parties to 6. • With linear adaptive measurement we can access the deterministic 3-bit AND function. • The triple product s1s2s3 of input bits s1, s2, s3. • With no adaptivity, deterministic computation of this function is impossible with only 6 measurements [1]. [1] In Hoban et al (2010 - arxiv next week) we show that 2^(n-1) qubits are required to acheive an n-bit AND deterministically with no adaptivity. linearlinear linear Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. • This enables one to consider a richer structure of quantum correlations in the context of BIs (including the adaptive measurements arising in MBQC) which we are only starting to investigate. Sunday, 1 August 2010 Summary • We derived Bell inequalities from the perspective of measurement-based quantum computation. • This allowed us to characterise all 2-setting, 2-output Bell inequalities in terms of the linear Boolean polytope. • And made it clear that extra linear computations (including simulated adaptivity) do not lead to loopholes. • This enables one to consider a richer structure of quantum correlations in the context of BIs (including the adaptive measurements arising in MBQC) which we are only starting to investigate. • Are Bell inequality violations more about non-linearity than non-locality...? Sunday, 1 August 2010 Acknowledgements • Joint work with members of my UCL group • Matty Hoban, Janet Anders, Earl Campbell and Klearchos Loukopoulos. • These ideas benefitted from discussions with Robert Raussendorf, Robert Spekkens, Miguel Navascues, Akimasa Miyake, Robin Blume-Kohout Debbie Leung and many others... • References • R. Werner and M. Wolf, Phys. Rev. A 64 32112 (2001) • J. Anders and D. E. Browne, Phys. Rev. Lett. (2009) • M. J. Hoban, E.T. Campbell, K. Loukopoulos, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalities", arxiv very very soon. • M. J. Hoban and D. E. Browne, Bell inequalities and adaptive measurements, arxiv soon. Sunday, 1 August 2010
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Correlations in Measurement-Based Quantum Computing...
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Correlations in Measurement-Based Quantum Computing and Bell Inequalities Browne, Daniel 2010-07-24
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Correlations in Measurement-Based Quantum Computing and Bell Inequalities |
Creator |
Browne, Daniel |
Contributor |
University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) |
Date Issued | 2010-07-24 |
Description | Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed. Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible. At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored. [1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009) [2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449 [3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation. [4] M. J. Hoban and D.E. Browne, in preparation. |
Genre |
Presentation |
Type |
Text Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103168 |
URI | http://hdl.handle.net/2429/30935 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Researcher |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 59370-Vancouver Invited Browne.pdf [ 1.21MB ]
- 59370-WS Jul 24 Browne.mp4 [ 149.56MB ]
- Metadata
- JSON: 59370-1.0103168.json
- JSON-LD: 59370-1.0103168-ld.json
- RDF/XML (Pretty): 59370-1.0103168-rdf.xml
- RDF/JSON: 59370-1.0103168-rdf.json
- Turtle: 59370-1.0103168-turtle.txt
- N-Triples: 59370-1.0103168-rdf-ntriples.txt
- Original Record: 59370-1.0103168-source.json
- Full Text
- 59370-1.0103168-fulltext.txt
- Citation
- 59370-1.0103168.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103168/manifest