Bell inequalities for (Measurement Based Quantum) Computation s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} Dan Browne Dept. of Physics and Astronomy University College London Sunday, 1 August 2010 (MeasurementBased) Quantum Computation Quantum Foundations 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 Prepare entangled resource state Measure a sub-set of qubits e.g. cluster state Process measurement results Choose bases for next subset of measurements Computational Output Requires classical “side-computation” Sunday, 1 August 2010 Measurement-based quantum computation sj ∈ {0, 1} cos θj X + (−1)sj sin θj Y +1 → 0 −1→1 mj ∈ {0, 1} R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). 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 sj ∈ {0, 1} cos θj X + (−1)sj sin θj Y and meas. outcomes are relabelled +1 → 0 −1→1 mj ∈ {0, 1} R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). 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 cos θj X + (−1)sj sin θj Y and meas. outcomes are relabelled • sj ∈ {0, 1} +1 → 0 −1→1 mj ∈ {0, 1} The angle θj is pre-set and differs for each measurement. R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). 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 cos θj X + (−1)sj sin θj Y and meas. outcomes are relabelled • • sj ∈ {0, 1} +1 → 0 −1→1 mj ∈ {0, 1} The angle θj is pre-set and differs for each measurement. But bit-value sj is calculated on the fly - and set equal to the parity of a sub-set of previous measurement outcomes. R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). 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 sj ∈ {0, 1} cos θj X + (−1)sj sin θj Y and meas. outcomes are relabelled +1 → 0 −1→1 mj ∈ {0, 1} • • The angle θj is pre-set and differs for each measurement. • Final output bits are encoded in the parity of a sub-set of the measurement outcomes. But bit-value sj is calculated on the fly - and set equal to the parity of a sub-set of previous measurement outcomes. R. Raussendorf, D. E. Browne and H.J. Briegel, PRA (2003). Sunday, 1 August 2010 Measurement-based quantum computation Prepare entangled resource state Measure a sub-set of qubits e.g. cluster state Process measurement results Choose bases for next subset of measurements Computational Output 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 Setting: s1 ∈ {0, 1} s2 ∈ {0, 1} Outcome: m1 ∈ {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 Setting: s1 ∈ {0, 1} s2 ∈ {0, 1} Outcome: m1 ∈ {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 ) • and show that for correlations in any LHV theory: Sunday, 1 August 2010 E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 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: √ E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 2 • A (loophole-free) demonstration of a Bell Inequality violation would refute local hidden variable theories. 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 • 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 = 4 B. S. Tsirelson, Lett. Math. Phys. (1980). S. Popescu and D. Rohrlich, Found. Phys. (1994) Sunday, 1 August 2010 CHSH inequality E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. Es1 ,s2 = p(m1 ⊕ m2 = 0|s1 , s2 ) − p(m1 ⊕ m2 = 1|s1 , s2 ) Sunday, 1 August 2010 CHSH inequality E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. Es1 ,s2 = p(m1 ⊕ m2 = 0|s1 , s2 ) − p(m1 ⊕ m2 = 1|s1 , s2 ) • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: 3 1 � p(m1 ⊕ m2 = s1 s2 |s1 s2 ) ≤ 4 s ,s 4 1 2 [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Sunday, 1 August 2010 CHSH inequality E0,0 + E0,1 + E1,0 − E1,1 ≤ 2 • It is useful to re-express the CHSH Inequality directly in terms of conditional probabilities. Es1 ,s2 = p(m1 ⊕ m2 = 0|s1 , s2 ) − p(m1 ⊕ m2 = 1|s1 , s2 ) • Some simple algebra gives us a very neat representation [1] of the CHSH inequality: 3 1 � p(m1 ⊕ m2 = s1 s2 |s1 s2 ) ≤ 4 s ,s 4 1 2 • Thus we can phrase the CHSH inequality in terms of a game. [1] QIP Folklore: earliest reference I know: Wim Van Dam, PHD Thesis (2000) Sunday, 1 August 2010 CHSH game • Rules: • Alice, Bob are given independent bits s , s 1 2 from a uniform distribution. • They may not communicate during the game. • Aim: • They should each produce a bit m , m 1 2, such that m1 ⊕ m2 = s1 s2 m1 XOR m2 = s1 AND s2 • We call games where the desired data is encoded in the XOR of measurement outcomes XOR-games. Sunday, 1 August 2010 CHSH game 1 � p(m1 + m2 = s1 s2 ) 4 s ,s 1 2 3 ≤ 4 √ 2+ 2 ≤ ≈ 0.85 4 =1 Sunday, 1 August 2010 LHV Quantum PR Box CHSH game • CHSH inequalities bound the mean success probability of the game. 1 � p(m1 + m2 = s1 s2 ) 4 s ,s 1 2 3 ≤ 4 √ 2+ 2 ≤ ≈ 0.85 4 =1 Sunday, 1 August 2010 LHV Quantum PR Box CHSH game • CHSH inequalities bound the mean success probability of the game. 1 � p(m1 + m2 = s1 s2 ) 4 s ,s 1 2 3 ≤ 4 √ 2+ 2 ≤ ≈ 0.85 4 =1 LHV Quantum PR Box • The GHZ paradox can also be related to a very similar game. Sunday, 1 August 2010 GHZ correlation |ψ� = |001� + |110� (uniquely) satisfies: X ⊗ X ⊗ X|ψ� = |ψ� X ⊗ Y ⊗ Y |ψ� = |ψ� Y ⊗ X ⊗ Y |ψ� = |ψ� which also imply: Y ⊗ Y ⊗ X|ψ� = −|ψ� } N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 Correlations in outcomes of local measurements GHZ correlation |ψ� = |001� + |110� (uniquely) satisfies: X ⊗ X ⊗ X|ψ� = |ψ� X ⊗ Y ⊗ Y |ψ� = |ψ� Y ⊗ X ⊗ Y |ψ� = |ψ� which also imply: Y ⊗ Y ⊗ X|ψ� = −|ψ� } N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 Correlations in outcomes of local measurements GHZ correlation |ψ� = |001� + |110� (uniquely) satisfies: X ⊗ X ⊗ X|ψ� = |ψ� X ⊗ Y ⊗ Y |ψ� = |ψ� Y ⊗ X ⊗ Y |ψ� = |ψ� which also imply: Y ⊗ Y ⊗ X|ψ� = −|ψ� } Correlations in outcomes of local measurements GHZ “Paradox”: No (non-contextual) real number assignment of X and Y can satisfy all of these. N. D. Mermin (1990), building on Greenberger, et al. (1989) Sunday, 1 August 2010 GHZ “paradox” • A very clean way to express this correlation is to use the binary notation introduced above. s1 s2 s1 + s2 m1 m2 m3 m1 ⊕ m2 ⊕ m3 = s1 s2 • I.e. the correlations “win” an XOR-game, nearly identical to the CHSH game. J. Anders and D. E. Browne PRL (2009). Sunday, 1 August 2010 Geometric approach to Bell inequalities Sunday, 1 August 2010 Geometric interpretation of BIs • Another useful representation of Bell inequalities is to form a vector from the conditional probabilities. p(s1 , s2 ) ≡ p(m1 ⊕ m2 = 1|s1 , s2 ) p(0, 0) p(0, 1) p� = p(1, 0) p(1, 1) • 1,1,1,1 conditional probability space 0,0,0,0 Each possible set of conditional probabilities is represented a point in a unit hypercube. Sunday, 1 August 2010 Geometric interpretation of BIs We can thus classify the regions of conditional probability space (2-D Schematic). PR Box Quantum region LHV region: “Bell polytope” Bell inequalities define facets of polytope. Marcel Froissart: Nouvo Cimento (1981), B.S. Tsirelson, J. Sov. Math. (1987) Sunday, 1 August 2010 Convex polytopes • The convex hull of a set of vectors (vertices) in R^d. Vertex Facet inequality Facet • 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.) 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 M= � mj j Sunday, 1 August 2010 m1 sn s2 m2 ··· mn 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 M= � mj j Sunday, 1 August 2010 m1 sn s2 m2 ··· mn 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 M= � mj j m1 • Sunday, 1 August 2010 sn s2 m2 ··· mn W & W derived the full n-party Bell polytope - and found that, for any n, it is a hyper-octahedron in 2^n dimensions. 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 Loopholes make the LHV region larger. Allowed LHV correlations under Bell’s assumptions Sunday, 1 August 2010 Loopholes in Bell Inequality experiments Loopholes make the LHV region larger. Allowed LHV correlations under Bell’s assumptions Sunday, 1 August 2010 Allowed LHV correlations under actual experimental conditions Bell inequalities vs Measurement-Based Quantum Computation Sunday, 1 August 2010 MBQC vs BIs s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs Sunday, 1 August 2010 MBQC vs BIs s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • Both • Require (only) XOR side-processing to perform computational game or task. • This task is impossible (non-linear) with XOR gates alone (linear gates). Sunday, 1 August 2010 MBQC vs BIs s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs Sunday, 1 August 2010 MBQC vs BIs s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • 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. Sunday, 1 August 2010 This talk s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • • 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: • Sunday, 1 August 2010 Polytopes over Boolean functions. 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 2 bit n vector listing the outputs for each of the 2n inputs. • E.g. f (0 . . . 00) f (0 . . . 01) f (0 . . . 10) � f = .. . f (1 . . . 11) to enumerate the Boolean functions • Itas is convenient where j =1, ..., 2^(2^n). 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 2 bit n vector listing the outputs for each of the 2n inputs. • E.g. f (0 . . . 00) f (0 . . . 01) f (0 . . . 10) � f = .. . • I.e. There 2^(2^n) Boolean functions. f (1 . . . 11) to enumerate the Boolean functions • Itas is convenient where j =1, ..., 2^(2^n). 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 2 bit n vector listing the outputs for each of the 2n inputs. • E.g. f (0 . . . 00) f (0 . . . 01) f (0 . . . 10) � f = .. . • I.e. There 2^(2^n) Boolean functions. f (1 . . . 11) to enumerate the Boolean functions • Itas isfconvenient (�s) where j =1, ..., 2^(2^n). j 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 = s1 s2 . . . sn f (s) = a0 + a1 s1 + a2 s2 + · · · + a12 s1 s2 + · · · 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 = s1 s2 . . . sn f (s) = a0 + a1 s1 + a2 s2 + · · · + a12 s1 s2 + · · · 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 = s1 s2 . . . sn f (s) = a0 + a1 s1 + a2 s2 + · · · + a12 s1 s2 + · · · • In other words, any Boolean function can be expressed as a sequence of XOR (add mod 2) and AND (multiply) gates. 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 = s1 s2 . . . sn f (s) = a0 + a1 s1 + a2 s2 + · · · + a12 s1 s2 + · · · • 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. Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � j=1 Sunday, 1 August 2010 aj sj ak ∈ {0, 1} Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � j=1 Sunday, 1 August 2010 aj sj ak ∈ {0, 1} Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � aj sj j=1 ak ∈ {0, 1} 2^(n+1) such functions, which we shall • There are thus l (�s) enumerate Sunday, 1 August 2010 k where k =1, ..., 2^(n+1). Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � aj sj j=1 ak ∈ {0, 1} 2^(n+1) such functions, which we shall • There are thus l (�s) enumerate k where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � aj sj j=1 ak ∈ {0, 1} 2^(n+1) such functions, which we shall • There are thus l (�s) enumerate k where k =1, ..., 2^(n+1). • All linear functions may be generated via XOR gates alone. • Linear functions are closed under composition. Sunday, 1 August 2010 Linear Boolean functions • Linear Boolean functions are degree 1 polynomials, and can be most generally written l(s) = a0 + n � aj sj j=1 ak ∈ {0, 1} 2^(n+1) such functions, which we shall • There are thus l (�s) enumerate k 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. Sunday, 1 August 2010 Stochastic Boolean maps given input string • Consider a stochastic machine which, λ s, outputs fj (�s) with probability �s Sunday, 1 August 2010 j. prob: λj choice: j fj (�s) Stochastic Boolean maps given input string • Consider a stochastic machine which, λ s, outputs fj (�s) with probability �s j. prob: λj choice: j fj (�s) • The probability that the output bit of the machine is 1, conditional upon the input s, is given by: � � p(1|�s) = λj p(fj (�s) = 1) λj = 1 j Sunday, 1 August 2010 j 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: p(fj (�s) = 1) = fj (�s) • Sunday, 1 August 2010 and thus obtain p(1|�s) = � j λj fj (�s) Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: p(fj (�s) = 1) = fj (�s) • and thus obtain • or equivalently p(1|�s) = � j p� = � j Sunday, 1 August 2010 λj fj (�s) λj f�j Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: p(fj (�s) = 1) = fj (�s) • and thus obtain p(1|�s) = � λj fj (�s) j • or equivalently p� = � λj f�j j • This is a convex combination of real-space vectors and thus a polytope, we call it the Boolean polytope. Sunday, 1 August 2010 Stochastic Boolean maps • We can simplify this expression, due to a very convenient identity: p(fj (�s) = 1) = fj (�s) • and thus obtain p(1|�s) = � λj fj (�s) j • or equivalently p� = � λj f�j j • 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. Sunday, 1 August 2010 The Linear Polytope �s Sunday, 1 August 2010 prob: λj choice: j lj (�s) The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: �s Sunday, 1 August 2010 prob: λj choice: j lj (�s) The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: prob: λj �s choice: j lj (�s) • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: p� = n+1 2� j=1 Sunday, 1 August 2010 λj l�j The Linear Polytope • Consider now a stochastic machine which can only implement linear functions: prob: λj �s choice: j lj (�s) • The output probability of a linear stochastic machine lies in the 2^(n+1) vertex polytope: p� = n+1 2� λj l�j j=1 • We shall call this the (n-bit) linear polytope. 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 s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • 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? Sunday, 1 August 2010 Bell inequalities for MBQC s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs Sunday, 1 August 2010 Bell inequalities for MBQC s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • If we allow side computation to be universal, we could access the full Boolean polytope with side computation alone. Sunday, 1 August 2010 Bell inequalities for MBQC s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • 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: Sunday, 1 August 2010 Bell inequalities for MBQC s1 ∈ {0, 1} s2 ∈ {0, 1} m1 ∈ {0, 1} m2 ∈ {0, 1} vs • 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. 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 m1 s2 m2 M= sn ··· � j Sunday, 1 August 2010 mj mn Bell inequalities for MBQC • What computations M (�s) 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. Sunday, 1 August 2010 LHV? Bell inequalities for MBQC • What computations M (�s) 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. Sunday, 1 August 2010 LHV? Bell inequalities for MBQC • What computations M (�s) 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. LHV? • Randomness arises in LHV theories by random assignment of the hidden variables. Sunday, 1 August 2010 Bell inequalities for MBQC • What computations M (�s) 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. LHV? • 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. Sunday, 1 August 2010 Bell inequalities for MBQC • First let us consider a single box. sj mj • The most general deterministic relationships between output and input can be written: mj = aj + bj mj aj ∈ {0, 1} bj ∈ {0, 1} • I.e. there are only 4 1-bit to 1-bit functions. Sunday, 1 August 2010 Bell inequalities for MBQC • If we associates bit a and b with each box, the most j j general expression for the output XOR bit M (�s) is s1 s2 m1 M= ··· m2 � mj = j M =a+ � j Sunday, 1 August 2010 sn � aj + j bj sj � j mn bj sj Bell inequalities for MBQC M (�s) = a + � j Sunday, 1 August 2010 bj sj Bell inequalities for MBQC M (�s) = a + • Sunday, 1 August 2010 We see � j bj sj Bell inequalities for MBQC M (�s) = a + • Sunday, 1 August 2010 We see • this is linear in s, � j bj sj Bell inequalities for MBQC M (�s) = a + • Sunday, 1 August 2010 We see • • � bj sj j this is linear in s, by suitable choice of aj and bj all 2^(n+1) linear functions can be achieved. Bell inequalities for MBQC M (�s) = a + • • Sunday, 1 August 2010 We see • • � bj sj j 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 Bell inequalities for MBQC M (�s) = a + • • We see • • bj sj j 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 • Sunday, 1 August 2010 � is the Linear Polytope. 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. • Are they the same polytope? Sunday, 1 August 2010 The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. The linear polytope vs the Werner Wolf polytope • • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • • Are they the same polytope? Sunday, 1 August 2010 The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). The linear polytope vs the Werner Wolf polytope • • The linear polytope is a hyper-octahedron with 2^(n+1) vertices. • • Are they the same polytope? • Our derivation is a computational reformulation of the traditional Bell inequalities. Sunday, 1 August 2010 The Werner-Wolf polytope is a hyper-octahedron with 2^(n+1) vertices. Yes! In fact, the derivation above is essentially a line-by-line recasting of Werner and Wolf (2001). 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 s1 + s2 m1 m2 m3 m1 ⊕ m2 ⊕ m3 = s1 s2 Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! s1 s2 s1 + s2 m1 m2 m3 m1 ⊕ m2 ⊕ m3 = s1 s2 • Why does this not induce a loophole? Sunday, 1 August 2010 An example: pre-processing in GHZ • Notice the third input depends upon the other two! s1 s2 s1 + s2 m1 m2 m3 m1 ⊕ m2 ⊕ m3 = s1 s2 • Why does this not induce a loophole? • In an experiment, we simulate the dependency using post-selection. Sunday, 1 August 2010 An example: GHZ • In an experimental test of GHZ, the third input is set at random. s1 s2 r m1 m2 m3 our data, and only keep • We then post-select r =s +s data where Sunday, 1 August 2010 1 . 2 An example: GHZ • In an experimental test of GHZ, the third input is set at random. s1 s2 r m1 m2 m3 our data, and only keep • We then post-select r =s +s data where 1 . 2 • Does this induce a detection loop-hole? No, it doesn’t... 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. r1 M =a+ � r2 bj rj j m1 m2 rn ··· mn • Let s be the input bit-string (provided by a referee, say). • We can post-select data such that each r is a linear j function of the bits in s. 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 Sunday, 1 August 2010 bj rj Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. M =a+ � bj rj j • M is linear in r . The r ’s are linear in s. Hence M is j linear in s. Sunday, 1 August 2010 j Linear measurement post-selection • Observation: This post-selection does not induce a loophole. • Reason: closure of linear maps under composition. M =a+ � bj rj j • M is linear in r . The r ’s are linear in s. Hence M is j j linear in s. • M remains inside the linear polytope and no loopholes are induced - the LHV region is no larger than before. Sunday, 1 August 2010 Linear measurement post-selection • Sunday, 1 August 2010 But we can go further. r1 r2 m1 m2 Linear measurement post-selection • • Sunday, 1 August 2010 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. r1 r2 m1 m2 Linear measurement post-selection • • Sunday, 1 August 2010 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. s1 m1 + s2 m1 m2 Linear measurement post-selection • • But we can go further. • Since mj are linear in r, M will remain within the linear polytope! Sunday, 1 August 2010 By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. s1 m1 + s2 m1 m2 Linear measurement post-selection • • But we can go further. • • Since mj are linear in r, M will remain within the linear polytope! Sunday, 1 August 2010 By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. This allows us to simulate linearly adaptive measurements, s1 m1 + s2 m1 m2 Linear measurement post-selection • • But we can go further. • • Since mj are linear in r, M will remain within the linear polytope! • Sunday, 1 August 2010 By the same reasoning, we can post-select r to be a linear function in both s and the measurement output bits mj. This allows us to simulate linearly adaptive measurements, s1 m1 + s2 m1 m2 And the linear polytope will still describe all LHV correlations. Computational Bell inequalities Sunday, 1 August 2010 Computational Bell Inequalities • Sunday, 1 August 2010 We can use these observations to generalise the traditional Bell inequalities. 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 Sunday, 1 August 2010 • • On a random m-bit input string s • 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. Given n 2-setting, 2-outcome space-like separated measurements 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 From LHV to Quantum Correlations • A significant strand of Bell inequality research has been to characterise the set of conditional probabilities / stochastic maps allowed within Quantum Mechanics. [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 From LHV to Quantum Correlations • 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. [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 From LHV to Quantum Correlations • 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. [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 From LHV to Quantum Correlations • 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? [1] Known as Tsirelson - Landau - Masanes region. Sunday, 1 August 2010 A bigger quantum set? From LHV to Quantum Correlations • Yes! • For a fixed n, • Allowing extra parties • Allowing linear post-selection (simulated adaptivity). • can increase the quantum region. Sunday, 1 August 2010 From LHV to Quantum Correlations • 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. 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 s s s 1 2 3 linear linear of input bits s1, s2, s3. linear • 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. 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 • • • Sunday, 1 August 2010 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) • M. J. Hoban and D. E. Browne, Bell inequalities and adaptive measurements, arxiv soon. 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.
- 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 Jul 24, 2010
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 |
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 Still Image Sound 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/ |
Aggregated Source Repository | 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}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103168/manifest