Apoorva Patel

11 January 2013, ICQIQC, IISc A. Patel, Quantum Computation: Particle and Wave Aspects of Algorithms ... A digital language routinely uses a tensor pr...

0 downloads 9 Views 164KB Size
Strategies for Quantum Algorithms Apoorva Patel Centre for High Energy Physics and Supercomputer Education and Research Centre Indian Institute of Science, Bangalore 11 January 2013, ICQIQC, IISc

A. Patel, Quantum Computation: Particle and Wave Aspects of Algorithms Resonance 16 (2011) 821-835 [arXiv:1108.1659]

Strategies for Quantum Algorithms – p. 1

Types of Computers Efficiency, stability and use of a computational paradigm depend on the nature of implemented physical interactions. Classical (particle dynamics): Discrete Boolean logic is implemented using digital circuits.

Strategies for Quantum Algorithms – p. 2

Types of Computers Efficiency, stability and use of a computational paradigm depend on the nature of implemented physical interactions. Classical (particle dynamics): Discrete Boolean logic is implemented using digital circuits. Wave (classical wave dynamics): Analog variables can superpose, interfere, disperse etc., and are convenient for differentiation and integration. Waves have been widely used in communications, and in simple analog computers (e.g. RLC circuits), but they have been left out of digital computation.

Strategies for Quantum Algorithms – p. 2

Types of Computers Efficiency, stability and use of a computational paradigm depend on the nature of implemented physical interactions. Classical (particle dynamics): Discrete Boolean logic is implemented using digital circuits. Wave (classical wave dynamics): Analog variables can superpose, interfere, disperse etc., and are convenient for differentiation and integration. Waves have been widely used in communications, and in simple analog computers (e.g. RLC circuits), but they have been left out of digital computation. Quantum (particle+wave dynamics): Unitary evolution is implemented using quantum states. Combination of particle and wave properties produces unusual correlations called entanglement.

Strategies for Quantum Algorithms – p. 2

Types of Computers Efficiency, stability and use of a computational paradigm depend on the nature of implemented physical interactions. Classical (particle dynamics): Discrete Boolean logic is implemented using digital circuits. Wave (classical wave dynamics): Analog variables can superpose, interfere, disperse etc., and are convenient for differentiation and integration. Waves have been widely used in communications, and in simple analog computers (e.g. RLC circuits), but they have been left out of digital computation. Quantum (particle+wave dynamics): Unitary evolution is implemented using quantum states. Combination of particle and wave properties produces unusual correlations called entanglement. Wave algorithms can be useful in situations where spatial resources are cheap and quantum algorithms are fragile. Strategies for Quantum Algorithms – p. 2

Factorisation and Superposition Discreteness is a characteristic property of particles. A digital language routinely uses a tensor product structure, e.g. N = 2n possible values are represented by log2 N bits. That exponentially reduces resources compared to the case where every value is assigned a distinct physical state.

Strategies for Quantum Algorithms – p. 3

Factorisation and Superposition Discreteness is a characteristic property of particles. A digital language routinely uses a tensor product structure, e.g. N = 2n possible values are represented by log2 N bits. That exponentially reduces resources compared to the case where every value is assigned a distinct physical state. Factorisation means using the same strategy for algorithms. When that is possible, the spatial resources can be reduced by a factor N/ log2 N , which is the maximal gain achievable in the “particle-like” implementation of algorithms. For x ∈ {0, 1}⊗n , x2i = xi , and any f (x) is a multi-variable polynomial with N = 2n terms.

Strategies for Quantum Algorithms – p. 3

Factorisation and Superposition Discreteness is a characteristic property of particles. A digital language routinely uses a tensor product structure, e.g. N = 2n possible values are represented by log2 N bits. That exponentially reduces resources compared to the case where every value is assigned a distinct physical state. Factorisation means using the same strategy for algorithms. When that is possible, the spatial resources can be reduced by a factor N/ log2 N , which is the maximal gain achievable in the “particle-like” implementation of algorithms. For x ∈ {0, 1}⊗n , x2i = xi , and any f (x) is a multi-variable polynomial with N = 2n terms.

Superposition is a characteristic property of waves. Advantage for an SIMD algorithm depends on the number of components that can be efficiently superposed. (Parallelism transfers the time complexity to the space one, and then superposition cuts down the spatial complexity.) Strategies for Quantum Algorithms – p. 3

A tensor product structure in the Hilbert space allows superposition of an exponentially large number of components using only polynomial resources, e.g. a uniform superposition of N components can be created with n qubits and n rotations: n  ⊗n 2P −1 |0i+|1i −n/2 √ |0i⊗n −→ |ii = 2 2 i=0

Strategies for Quantum Algorithms – p. 4

A tensor product structure in the Hilbert space allows superposition of an exponentially large number of components using only polynomial resources, e.g. a uniform superposition of N components can be created with n qubits and n rotations: n  ⊗n 2P −1 |0i+|1i −n/2 √ |0i⊗n −→ |ii = 2 2 i=0

Reduction in temporal resources by a factor N/ log2 N is the maximal gain achievable in the “wave-like” implementation of algorithms. The caveat is that the final measurement can extract only one specific property of the output components (by interference, amplification or otherwise).

Strategies for Quantum Algorithms – p. 4

A tensor product structure in the Hilbert space allows superposition of an exponentially large number of components using only polynomial resources, e.g. a uniform superposition of N components can be created with n qubits and n rotations: n  ⊗n 2P −1 |0i+|1i −n/2 √ |0i⊗n −→ |ii = 2 2 i=0

Reduction in temporal resources by a factor N/ log2 N is the maximal gain achievable in the “wave-like” implementation of algorithms. The caveat is that the final measurement can extract only one specific property of the output components (by interference, amplification or otherwise). Classical algorithms can use either factorisation or superposition. Quantum algorithms can use both, but the gains of factorisation and superposition may overlap. Strategies for Quantum Algorithms – p. 4

Shor’s Algorithm Fourier Transform multiplies an N -component vector by an N × N matrix, which naively requires O(N 2 ) operations. It can also be viewed as a unitarychange of basis.  P 2πixy/N P P P 1 √ f (x) |yi xe x f (x)|xi = y F (y)|yi = y N

Strategies for Quantum Algorithms – p. 5

Shor’s Algorithm Fourier Transform multiplies an N -component vector by an N × N matrix, which naively requires O(N 2 ) operations. It can also be viewed as a unitarychange of basis.  P 2πixy/N P P P 1 √ f (x) |yi xe x f (x)|xi = y F (y)|yi = y N Let N = 2n , and apply the same tricks as in FFT. In binary notation, x = xn−1 · 2n−1 + . . . + x1 · 2 + x0 . frac( xy N ) = yn−1 (.x0 ) + yn−2 (.x1 x0 ) + . . . + y0 (.xn−1 . . . x0 ).

Strategies for Quantum Algorithms – p. 5

Shor’s Algorithm Fourier Transform multiplies an N -component vector by an N × N matrix, which naively requires O(N 2 ) operations. It can also be viewed as a unitarychange of basis.  P 2πixy/N P P P 1 √ f (x) |yi xe x f (x)|xi = y F (y)|yi = y N Let N = 2n , and apply the same tricks as in FFT. In binary notation, x = xn−1 · 2n−1 + . . . + x1 · 2 + x0 . frac( xy N ) = yn−1 (.x0 ) + yn−2 (.x1 x0 ) + . . . + y0 (.xn−1 . . . x0 ). P 2πixy/N 1 |yi Unitary rotation of QFT is: |xi → √N y e 0 ) |1i) (|0i+e2πi(.x1 x0 ) |1i) ( |0i+e2πi(.xn−1 ...x0 ) |1i) (|0i+e2πi(.x √ √ √ . . . = 2 2 2 Factorisation reduces QFT to n single qubit rotations. Full factorisation gives the maximal O(N/ log2 N ) gain. Strategies for Quantum Algorithms – p. 5

Shor’s Algorithm (contd.) Fourier transform for different values of x can be evaluated in parallel. In the “period finding” problem, the different values of x are processed in superposition, and the output components are cleverly combined into a single result.

Strategies for Quantum Algorithms – p. 6

Shor’s Algorithm (contd.) Fourier transform for different values of x can be evaluated in parallel. In the “period finding” problem, the different values of x are processed in superposition, and the output components are cleverly combined into a single result. Period finding is possible with maximal superposition of all the x values and a single run of QFT. So superposition also gives the maximal O(N/ log2 N ) gain.

Strategies for Quantum Algorithms – p. 6

Shor’s Algorithm (contd.) Fourier transform for different values of x can be evaluated in parallel. In the “period finding” problem, the different values of x are processed in superposition, and the output components are cleverly combined into a single result. Period finding is possible with maximal superposition of all the x values and a single run of QFT. So superposition also gives the maximal O(N/ log2 N ) gain. Factorisation over y and superposition over x are completely independent. With both gains attaining their maximal values, the algorithmic complexity reduces from O(N 2 ) to O((log2 N )2 ).

Strategies for Quantum Algorithms – p. 6

Grover’s Algorithm This is a relativised problem to search for a specific object in a database using binary oracle queries. In absence of any structure, random pickings give hQi = N .

Strategies for Quantum Algorithms – p. 7

Grover’s Algorithm This is a relativised problem to search for a specific object in a database using binary oracle queries. In absence of any structure, random pickings give hQi = N .

The digital strategy for improving the process is to factorise the oracle query into smaller parts, and then sort the database in the order of the query parts, e.g. a dictionary. A binary search tree achieves maximal factorisation with Q = log2 N . (Effort of sorting is not counted in complexity.)

Strategies for Quantum Algorithms – p. 7

Grover’s Algorithm This is a relativised problem to search for a specific object in a database using binary oracle queries. In absence of any structure, random pickings give hQi = N .

The digital strategy for improving the process is to factorise the oracle query into smaller parts, and then sort the database in the order of the query parts, e.g. a dictionary. A binary search tree achieves maximal factorisation with Q = log2 N . (Effort of sorting is not counted in complexity.) Subsequent parallelism can only be over possibilities addressed by each query factor. Wave dynamics can uniquely identify four objects using a single binary query. The additional gain of superposition is then log2 4 = 2. (Commutativity of superposition makes sorting redundant.)

Strategies for Quantum Algorithms – p. 7

Grover’s Algorithm (contd.) For an unsorted database, the oracle query cannot be factorised, and the only gain available is from superposition. Amplitude amplification relies on clever interference and does not have the SIMD structure. The achievable gain of √ superposition is O( N ) (not the maximal value N/ log2 N ). Grover’s algorithm can be executed by classical waves, √ with time complexity Q = O( N ), and space complexity N .

Strategies for Quantum Algorithms – p. 8

Grover’s Algorithm (contd.) For an unsorted database, the oracle query cannot be factorised, and the only gain available is from superposition. Amplitude amplification relies on clever interference and does not have the SIMD structure. The achievable gain of √ superposition is O( N ) (not the maximal value N/ log2 N ). Grover’s algorithm can be executed by classical waves, √ with time complexity Q = O( N ), and space complexity N . Search problem does not have two independent factors of N in its complexity for factorisation and superposition to act on. The overlap between the two limits the maximal gain to  : first F then S (N/ log2 N ) × 2 √ √ √ 2N/ log2 N = (N/ N ) × ( N / log2 N ) : first S then F Strategies for Quantum Algorithms – p. 8

Role of Entanglement Entangled quantum states are superposition of many digitally factorised states (in a chosen classical basis).

Strategies for Quantum Algorithms – p. 9

Role of Entanglement Entangled quantum states are superposition of many digitally factorised states (in a chosen classical basis). When the superposed components evolve independently (in the SIMD mode), the complexity gain is maximal. Feynman path integral framework provides a natural setting for such an implementation.

In the design of best quantum algorithms, non-mixing of the superposed components during evolution is important, and not the amount of entanglement.

Strategies for Quantum Algorithms – p. 9

Role of Entanglement Entangled quantum states are superposition of many digitally factorised states (in a chosen classical basis). When the superposed components evolve independently (in the SIMD mode), the complexity gain is maximal. Feynman path integral framework provides a natural setting for such an implementation.

In the design of best quantum algorithms, non-mixing of the superposed components during evolution is important, and not the amount of entanglement. Considerations of entanglement are relegated to the ends of the algorithm, i.e. the production of the initial superposed state and the choice of the final measurement operation. Initial superposition of states is often easy to achieve, but final extraction of the desired result by clever manipulation of the superposed outcomes is hard. Strategies for Quantum Algorithms – p. 9

Good efficiency requires shrinking of a distribution over N components to a small set, say a δ−function.

Strategies for Quantum Algorithms – p. 10

Good efficiency requires shrinking of a distribution over N components to a small set, say a δ−function. With no pattern, Grover’s algorithm is the optimal solution. A periodic pattern is easily converted to a δ−function by Fourier transform. Any other trick to produce a δ−function?

Strategies for Quantum Algorithms – p. 10

Good efficiency requires shrinking of a distribution over N components to a small set, say a δ−function. With no pattern, Grover’s algorithm is the optimal solution. A periodic pattern is easily converted to a δ−function by Fourier transform. Any other trick to produce a δ−function?

Lessons: Each of “particle-like” digital factorisation and “wave-like” parallelism can provide a complexity gain upto N/ log2 N . Best quantum algorithms would need problems with two non-overlapping factors of N to get the best out of both factorisation and superposition.

Strategies for Quantum Algorithms – p. 10

Good efficiency requires shrinking of a distribution over N components to a small set, say a δ−function. With no pattern, Grover’s algorithm is the optimal solution. A periodic pattern is easily converted to a δ−function by Fourier transform. Any other trick to produce a δ−function?

Lessons: Each of “particle-like” digital factorisation and “wave-like” parallelism can provide a complexity gain upto N/ log2 N . Best quantum algorithms would need problems with two non-overlapping factors of N to get the best out of both factorisation and superposition. General framework to do that for arbitrary problems is not available. But construction and optimisation of pure “wave algorithms” would be an excellent stepping stone. Strategies for Quantum Algorithms – p. 10

Many Body Systems Quantum wavefunctions for systems of identical particles have specific symmetry properties under permutations. Fermion wavefunctions are antisymmetric determinants: P Det(A) = i1 ,i2 ,...,in ǫi1 i2 ...in A1i1 A2i2 . . . Anin Boson wavefunctions are fully symmetric permanents: P P erm(A) = i1 ,i2 ,...,in ǫ2i1 i2 ...in A1i1 A2i2 . . . Anin

Strategies for Quantum Algorithms – p. 11

Many Body Systems Quantum wavefunctions for systems of identical particles have specific symmetry properties under permutations. Fermion wavefunctions are antisymmetric determinants: P Det(A) = i1 ,i2 ,...,in ǫi1 i2 ...in A1i1 A2i2 . . . Anin Boson wavefunctions are fully symmetric permanents: P P erm(A) = i1 ,i2 ,...,in ǫ2i1 i2 ...in A1i1 A2i2 . . . Anin

Determinants are easy to compute. Gaussian elimination provides an O(n3 ) algorithm. Permanents are hard to compute. Even with 0/1 entries, they belong to class #P . In complexity, #P problems are harder than N P -complete problems.

(Valiant, 1979)

Strategies for Quantum Algorithms – p. 11

Many Body Systems Quantum wavefunctions for systems of identical particles have specific symmetry properties under permutations. Fermion wavefunctions are antisymmetric determinants: P Det(A) = i1 ,i2 ,...,in ǫi1 i2 ...in A1i1 A2i2 . . . Anin Boson wavefunctions are fully symmetric permanents: P P erm(A) = i1 ,i2 ,...,in ǫ2i1 i2 ...in A1i1 A2i2 . . . Anin

Determinants are easy to compute. Gaussian elimination provides an O(n3 ) algorithm. Permanents are hard to compute. Even with 0/1 entries, they belong to class #P . In complexity, #P problems are harder than N P -complete problems.

(Valiant, 1979)

Given a sufficiently non-trivial multi-boson wavefunction, as the initial state of the physical hardware of a quantum computer, what type of problems can be easily solved? (Say using one-way computation strategy.) Strategies for Quantum Algorithms – p. 11

Graph Isomorphism A graph is defined by its vertices and edges, (V, E). Typical representation uses the 0/1 adjacency matrix. Two graphs are isomorphic iff they can be related by a relabeling (permutation) of the vertices.

Strategies for Quantum Algorithms – p. 12

Graph Isomorphism A graph is defined by its vertices and edges, (V, E). Typical representation uses the 0/1 adjacency matrix. Two graphs are isomorphic iff they can be related by a relabeling (permutation) of the vertices. The problem is believed to have computational complexity intermediate between P and N P -complete. Best known classical algorithm for n vertices is O(c



n log n ).

Restricted cases are in P : Bounded degree, bounded genus, bounded eigenvalue multiplicity etc. The special case of distinguishing “strongly regular" graphs √ 3 is not the most general, but still difficult, O(n n log n ).

Strategies for Quantum Algorithms – p. 12

Graph Isomorphism A graph is defined by its vertices and edges, (V, E). Typical representation uses the 0/1 adjacency matrix. Two graphs are isomorphic iff they can be related by a relabeling (permutation) of the vertices. The problem is believed to have computational complexity intermediate between P and N P -complete. Best known classical algorithm for n vertices is O(c



n log n ).

Restricted cases are in P : Bounded degree, bounded genus, bounded eigenvalue multiplicity etc. The special case of distinguishing “strongly regular" graphs √ 3 is not the most general, but still difficult, O(n n log n ). Well-known applications are in chemical structure identification and electronic circuit design. Strategies for Quantum Algorithms – p. 12

Graph Invariants The solution to the problem involves construction of graph invariants (under permutations), which must be the same for isomorphic graphs (e.g. degree of vertices). Higher order invariants are typically constructed recursively, th order starting from the adjacency matrix. In particular, k  n invariant requires k computational effort.

Strategies for Quantum Algorithms – p. 13

Graph Invariants The solution to the problem involves construction of graph invariants (under permutations), which must be the same for isomorphic graphs (e.g. degree of vertices). Higher order invariants are typically constructed recursively, th order starting from the adjacency matrix. In particular, k  n invariant requires k computational effort. These invariants can be obtained from the spectra of Hamiltonians describing k -particle walks on the graph.

(T. Rudolph, quant-ph/0206068)

Hubbard Model :

H=

X i,j

Aij c†i cj

+V

X i

(c†i ci )(c†i ci − 1)

Without interactions, the quantum wavefunction factorises.

Strategies for Quantum Algorithms – p. 13

Graph Invariants The solution to the problem involves construction of graph invariants (under permutations), which must be the same for isomorphic graphs (e.g. degree of vertices). Higher order invariants are typically constructed recursively, th order starting from the adjacency matrix. In particular, k  n invariant requires k computational effort. These invariants can be obtained from the spectra of Hamiltonians describing k -particle walks on the graph.

(T. Rudolph, quant-ph/0206068)

Hubbard Model :

H=

X i,j

Aij c†i cj

+V

X i

(c†i ci )(c†i ci − 1)

Without interactions, the quantum wavefunction factorises. −itH has spectral information. The evolution operator U = e  n The k effort is parallelised in a quantum algorithm.

Strategies for Quantum Algorithms – p. 13

Lifting the Degeneracy Spectrum of the nearest neighbour hopping Hamiltonian (adjacency matrix) for Strongly Regular Graph (16,6,2,2). (J. Gamble et al., PRA 81 (2010) 052313)

(i) A single particle (ii) Two non-interacting fermions (iii) Two non-interacting bosons (iv) Two bosons with hard-core repulsion

Strategies for Quantum Algorithms – p. 14

Lifting the Degeneracy Spectrum of the nearest neighbour hopping Hamiltonian (adjacency matrix) for Strongly Regular Graph (16,6,2,2). (J. Gamble et al., PRA 81 (2010) 052313)

(i) A single particle (ii) Two non-interacting fermions (iii) Two non-interacting bosons (iv) Two bosons with hard-core repulsion Challenge: Find interacting boson Hamiltonians that maximally lift spectral degeneracies. Strategies for Quantum Algorithms – p. 14