Applications of Multi-Valued Quantum Algorithms Yale Fan ISMVL 2007

Applications of Multi-Valued Quantum Algorithms Yale Fan ISMVL 2007

Quantum Robotics for Teenagers Project at PSU Yale Fan, 14 years old, talks about his motivation for this project Contents: Introduction Binary Deutsch-Jozsa Algorithm Multi-valued Deutsch-Jozsa Algorithm Binary Grover Algorithm Multi-valued Grover Algorithm Time 40 seconds

Contents: Introduction Binary Deutsch-Jozsa Algorithm Multi-valued Deutsch-Jozsa Algorithm Binary Grover Algorithm Multi-valued Grover Algorithm

Review of Quantum Computing Fundaments Algorithms for quantum computing involve the unitary evolution of the state vector representing a quantum system, implemented in a reversible circuit. Mathematically, a superposed quantum system can be described by a state vector in the n-dimensional Hilbert space Hn with each of its possible states at measurement being a vector in the standard basis of that Hilbert space: i i i Whereas in binary quantum computing, only the unitary evolution of state vectors in Hilbert space Hd where d 2k are considered, the mathematical formulation of quantum computing in multi-valued logic can involve Hilbert spaces of arbitrary dimensions.

The Hadamard Transform vs. QFT The action of the Hadamard transform on either of the basis states (vectors) in two-dimensional Hilbert space produces two different superpositions: The basic Hadamard matrix: H 1 1 1 2 1 1 H 0 1 1 1 1 1 (0 1) 2 1 1 0 2 H1 1 1 1 0 1 (0 1) 2 1 1 1 2 The negative sign merely indicates a difference in the phase of the complex amplitude of this state The quantum Fourier transform (QFT) of order n over the primitive nth roots of unity ω ei2π/n has the following matrix: 1 n 1 n 1 i 2 jk / n Fn e n j 0 k 0 1 1 1 2 1 1 j k 1 2 4 n 1 n 1 2 ( n 1) i2π/n the primitive nth roots of unity ω e 1 n 1 2 ( n 1) ( n 1)( n 1) Both of these transforms are integral to many quantum algorithms because by implementing quantum superposition, they allow for simultaneous computations on a superposed quantum data register on very large scales.

The Deutsch-Jozsa Problem: The Deutsch-Jozsa Problem: Is a given Boolean function f : {0, 1}r {0, 1} constant or balanced, when promised that it is either? 1. Constant means f (x) some c for all x 2. Balanced means f (x) 0 for half (2r-1) of the codomain values, otherwise f (x) 1 ORACLE: Unitary circuit for implementing f (x) y Uf x x With as few queries to the oracle as possible, determine whether f (x) is constant or balanced. y f (x)

Classical Solution When considering the simplest “degenerate” case of f : {0, 1} {0, 1}: f (x) is balanced iff f (0) f (1) 1 f (x) is constant iff f (0) f (1) 0 Obtaining f (0) and f (1) requires two function evaluations In testing for constant or balanced functions with 2r possible outputs, 2r-1 1 tests are required classically: A B 00 01 10 11 00 1 1 0 0 01 1 1 0 0 10 1 1 0 0 11 1 1 0 0 Balanced (Worst case) A B 00 01 10 11 00 1 1 0 0 01 1 1 0 0 10 1 1 0 0 11 1 1 0 0 Balanced (Best case) A B 00 01 10 11 00 1 1 1 1 01 1 1 1 1 10 1 1 1 1 11 1 1 1 1 Constant (Indeterminate) The outputs are plotted in Marquand charts above, akin to Karnaugh maps but without Gray code

Quantum Solution to binary Deutsch-Jozsa 0 1 x 2 f ( x) 1 f ( x) 0 1 f ( x) x Uf x ( 1) 2 2 1 x H 0 (0 1) 2 1 y H 1 (0 1) 2 x ORACLE y f (x) ( 1) f ( x ) x Putting this through another Hadamard transform gives the quantum state f (0) f (1) deterministically in a single measurement, which determines the constancy of the function 1 (0 1) 2 Therefore, the plan of attack for the general case of f : {0, 1}r {0, 1} where time complexity is exponential is to put the x-register into a superposition of all states corresponding to bit strings in the domain of the function.

Overview 1) Quantum Hadamard gates superpose all information states for parallel computation on r wires 2) The oracle computes the function on all states simultaneously and XORs the result with each bit in the superposed ancillary register The Deutsch-Jozsa Circuit *In the sense that one can deterministically infer from the output whether the function is constant or balanced 3) Quantum Hadamard gates collapse the register (deterministic output)*

Binary Deutsch-Jozsa, in Steps r x 0 H x r Uf H y 1 Ψ1 H r y f (x) Ψ2 H Ψ3 Ψ1 : Initialize registers to x 0 r , y 1 Ψ2 : ( H 0 ) r H 1 2r 1 1 2 r x 0 x y 2r 1 1 2 r x 0 0 1 x 2 Ψ4

Binary Deutsch-Jozsa, cont. r x 0 H Ψ1 Ψ3 : 1 2r 2r 1 2 r 2r 1 Ψ2 x y f ( x) x 0 ( 1) f ( x) x 0 Ψ4 : Uf H y 1 1 x r H 0 1 x 2 r 1 H r y f (x) H Ψ3 1 2 r 1 2r 1 Ψ4 x ( f ( x) 1 f ( x) ) x 0 If f (x) is constant, then the state vector of the x-register will be a linear combination of basis states with both equal amplitudes and phases, which results in the state 00 00 if passed through another Hadamard transform. 3 x1 , x2 ,., xr 1 The output of the ancillary y-register is now discarded (in fact, the last Hadamard gate on the bottom wire is unnecessary) If any qubits in the query (x) register are 1 at output, then f (x) is balanced; otherwise, it is constant.

Advantage of Binary Quantum Deutsch-Jozsa over Classical Algorithms Using quantum parallelism, the Deutsch-Jozsa algorithm is able to determine whether a Boolean function f (x) with an r-qubit query register for x is constant or balanced using a single measurement.

Yale talks about the purpose of multiple-valued logic in quantum computing

Quantum n-valued Multiplexer, Muthukrishnan-Stroud (M-S) Gate: If A n - 1 then Q fn - 1(B) else Q B A 0 1 B P fn - 1 n-1 The schematic k Q is shorthand for the M-S gate implementing fn - 1(x) (x k) mod n Muthukrishnan-Stroud gates can be used in the following quantum circuits to implement multi-valued “logical” functions in oracles. This treatment of multi-valued logic is not restricted to Galois fields and powers of prime radices, but simply the additive group Zn (which has less restraints on dimension).

A Basic Building Block of Quantum Circuits: The Feynman Gate The binary quantum Feynman gate is capable of simulating XOR as a controlled inverter while preserving circuit reversibility (i.e., a one-to-one mapping between input and output vectors). Only if the control bit A is 1 will B be inverted. A P B Q A 0 0 1 1 B 0 1 0 1 P 0 0 1 1 Q 0 1 1 0 {P, Q} {A, A Multi-Valued (Ternary) Synthesis of Feynman Gate (Controlled NOT): X1 X2 Y1 X 1 Y2 X 1 X 2 (a) Symbol X1 1 X 2 2 2 Y1 Y2 1 (b) Realization B}

Another Basic Building Block: The Toffoli Gate The binary quantum Toffoli gate is capable of simulating AND as a double-controlled inverter with ancillary bit 0. A P B Q C R A 0 0 1 1 B 0 1 0 1 C 0 0 0 0 P 0 0 1 1 Q 0 1 0 1 X1 X2 X3 2 2 2 Y1 X 1 Y2 X 2 Y3 X 3 Z transform of X 4 if ( i) X i 2 X4 Z Y4 otherwise X 4 (a) Symbol Inverse gates X1 Y1 X2 Y2 X3 Y3 0 1 1 2 2 0 0 0 1 1 2 2 X4 Y4 Z R 0 0 0 1 (P, Q) (A, B), R AB Multi-Valued (Ternary) Synthesis of Toffoli Gate (Triple-Controlled NOT): C (b) Realization using M-S gates

xtensions to multiple-valued logic by Definitio An r-qudit multi-valued function of the form f : {0,1, , n 1}r {0,1, , n 1} r is constant when f ( x) f ( y ) x, y {0,1, , n 1} and is balanced when an equal number of the nr domain values, namely nr – 1, is mapped to each of the n elements in the codomain. Multi-valued affine logical functions are defined as f ( x1 , , xr ) A0 A1 x1 Ar xr where A0 , , Ar Ζ n denotes addition modulo n, a generalization of the XOR operator to higher-radix logic. The AND operator can also be generalized naturally by modulo-n multiplication.

Multi-Valued Deutsch-Jozsa

The Multi-Valued Deutsch-Jozsa Circuit See the multi-valued Grover circuit for an explanation of this operator QFT n 1 1 k k n k 0 U i0 1 n 1 k k n k 0 Here, information about the function is encoded in the phase of the amplitude of each basis state, which is “revealed” after the second set of QFTs

An example of multi-valued Deutsch-Jozsa for texture classification in image processing Consider a simple texture of 3 colors: *A classical computer would require at least 18 9 lg 3 bits to classify this texture Minimum representative pixel map *Using the multi-valued Deutsch-Jozsa algorithm, a quantum computer would require only a single information state (a configuration of a 2-qutrit system) to distinguish this texture from all others, by encoding it as a multivalued affine function

The oracle Uf contains the following affine function defined on two qutrits AB , whose Marquand chart representation can be used to encode each pixel: A 0 0 1 1 2 2 0 B 1 0 1 2 2 2 0 1 Only considering the x-register (since the ancillary register is discarded at output), the states of the algorithm are as follows (beginning at Ψ3 , after the states have been initialized): 3 U f ( Fn 2 2 1 1 1 2 0 ) 3 1 2 4 Fn 2 3 0 0 0 0 0 2 21 0 0 2 0 We can now derive a closed expression for the affine function in the oracle, save for the constant term, by taking{2, 1} as the respective coefficients A1 and A2. The constant term A0 is insignificant, since it only corresponds to the choice of minimum representative pixel map for the texture, of which there are 3 choices (although for this particular example, A0 would be (-2) mod 3 1): f ( x1 , x2 ) (Constant ) 2 x1 x2 Note that the two-qutrit state 21 , which has essentially the cost of two bits, can now be used to succinctly encode this texture, as opposed to the 18 bits required classically.

The multi-valued Deutsch-Jozsa algorithm used for “error correction” in image processing Given a texture (encoded in a balanced logical function) with slight noise, the algorithm probabilistically infers the correct texture encoded in an affine logical function. A 0 0 0 1 2 2 1 B 1 1 0 2 2 2 0 1 1 2 Using the balanced function defined by the Marquand chart at left to encode the noisy image (1), we obtain the following state at output: 4 1 2 1 2 2 1 01 02 11 12 21 22 3 3 3 3 3 3 A The basis state 12 hence has the highest probability of measurement (4/9), with all others having 1/9. The Marquand chart for the two-qutrit affine function associated with the output state 12 represents the correct texture (2): f ( x1 , x2 ) x1 2 x2 0 0 0 1 2 2 1 B 1 1 0 2 2 2 1 0

Yale talks about history of his work and his thought processes while working on Deutsch and next moving to Grover algorithm – 2 minutes

Grover’s Problem Grover’s Problem: Given an unsorted database of size N, where is the desired element? A classical linear search requires an average of N/2 tries, and thus O(N) time, while a quantum “parallel” search reduces this to O( N)

Overview 1) Quantum Hadamard gates superpose all elements in the search space 2) The G operator increases the amplitude of the searched element, encoded in a quantum state First register (r qubits) Ancillary register (1 qubit) The Grover Circuit 3) The searched state will be measured at output with very high probability

Detail of the G operator Inputs a superposed data register The oracle marks the searched state via phase rotation Same in structure to that of the Deutsch-Jozsa algorithm The diffusion operator increases the amplitude via inversion about the average amplitude Dirac notation for the corresponding unitary operator, where ( H 0 ) r (an equal superposition of all states)

Geometric visualization of the G iteration in real subspace of 2-D (“binary”) Hilbert space Searched State Other Elements in Search Space Each G-iteration rotates the state vector of the search space through a constant angle

Amplitudes of bits after Hadamard For every bit All possible states

Amplitudes of bits after one stage of G (Oracle) (Diffusion operator)

Multi-Valued Grover Algorithm This phase rotation operator is also “invoked” from the oracle by the y-register in the multi-valued Deutsch-Jozsa algorithm, but since only one output of the Boolean function in Uf is unique in the case of Grover’s algorithm, it rotates the phase of only the searched state i0 by –2π/n Amplifies amplitude of searched state U i0 The Multi-Valued Grover operator The Grover algorithm in multi-valued logic still provides a quadratic speedup over classical algorithms

iterations 2; Simple MATLAB script for simulation of Grover’s algorithm; n is radix, r is no. of qudits, n r is search space size, i 0 is searched element n r N i 0 3; 2; n r; 5; for j 1:n for k 1:n F(j,k) exp(i*2*pi*(j-1)*(k-1)/n)/sqrt(n); end end F tensor F; t 1; while t r F tensor kron(F tensor, F); t t 1; end U f eye(N,N); U f(i 0,i 0) exp(-i*2*pi/n); For computational efficiency, simply initialize psi to D (1 - exp(-i*2*pi/n))*(1/N)*ones(N,N) - eye(N,N); (1/sqrt(N))*ones(1,N)’ init state zeros(1,N)'; init state(1,1) 1; G D*U f; psi F tensor*init state; output (G iterations)*psi

Comparisons for different radices and search space sizes in MATLAB: No. of qudits (register size) Note that the binary case has the lowest probability of success, while the ternary case searches a larger search space, yet requires the same number of iterations. The binary case also requires the largest register. iterations 2; iterations 5; iterations 2; n r N i 0 n r N i 0 n r N i 0 3; 2; n r; 5; 8; 1; n r; 5; 2; 3; n r; 5; -------------------- -------------------- -------------------- output output output -0.0185 -0.0185 -0.0185 -0.0185 -0.0185 -0.0185 -0.0185 -0.0185 -0.0185 0.0321i 0.0321i 0.0321i 0.0321i 0.9943i 0.0321i 0.0321i 0.0321i 0.0321i 0.0196 0.0196 0.0196 0.0196 -0.3578 0.0196 0.0196 0.0196 - 0.0196i 0.0196i 0.0196i 0.0196i 0.9309i 0.0196i 0.0196i 0.0196i -0.0884 -0.0884 -0.0884 -0.0884 0.9723 -0.0884 -0.0884 -0.0884 - 0.0000i 0.0000i 0.0000i 0.0000i 0.0000i 0.0000i 0.0000i 0.0000i abs(output(5)) 2 abs(output(5)) 2 ans ans abs(output(5)) 2 ans Probability of measuring searched state 0.9946 0.9453 0.9890 abs(output(1)) 2 abs(output(1)) 2 ans ans abs(output(1)) 2 ans Probability of measuring any other state 7.7170e-004 0.0014 0.0078

Yale derives part of his multiple-valued generalization of Grover. – 7 minutes

The multi-valued Grover algorithm could be applied to any general search problem because the Boolean function implemented by the oracle can be modified to represent any parameters. MV Grover for Graph Coloring In searching for a valid coloring of a planar map (where no two adjacent regions are of the same color), any coloring of the corresponding graph with s vertices could be encoded in a string of s radix-4 digits; hence, the 4valued Grover algorithm would be most efficient in terms of memory register size (encoding).

1 A Simple Graph Coloring Problem 3 2 4 Perform QFT on each wire to obtain a superposition of all states, or the set of all possible colorings Find a valid coloring of the graph at left, given its chromatic number is 3 Ternary Grover Oracle Only one ternary quantum wire is needed to encode the color of each vertex (in binary logic, this problem would require two wires and thus one wasted information state) F3 F3 F3 F3 This predicate returns “1” when vertices 1 and 2 have different colors (encodings) 1 2 1 3 2 3 2 4 3 4 f (x) AND gate synthesized from multi-valued Toffoli gate Returns “1” for a valid coloring

An Example of the 10-Valued Grover Algorithm for a Simple Cryptographic Puzzle A well-known problem of constraint satisfiability Carries S E N D M O R Y c3 c 2 c1 SEND MORE MONEY Find an injective mapping {S , E , N , D, M , O, R, Y } {0,1,2,3,4,5,6,7,8,9} and a surjective mapping {c1 , c2 , c3} {0,1} such that: Inverse c1 c2 c3 QFT goes here 1. (D E) mod 10 Y; if D Y, c1 1 else c1 0 2. (c1 N R) mod 10 E; if N E, c2 1 else c2 0 3. (c2 E O) mod 10 N; if E N, c3 1 else c3 0 4. (c3 S M) mod 10 O 5. S O 0 This Grover oracle combines 10-valued qudits and modulo-10 operators synthesized from Feynman gates with binary predicates whose outputs control a binary Toffoli gate to form a logically “hybrid” circuit. Output “1” for valid mapping

The Grover algorithm could also be effectively applied to the NP-complete Boolean satisfiability (SAT) problem. Any arbitrary Boolean formula can be used as the function that the oracle uses to mark the searched quantum state (encoded in the particular substitution of literals that satisfies the expression). A great number of search-related problems in NP can be reduced to SAT. Example of a Grover oracle architecture for solving an instance of the 3-SAT problem (given a Boolean expression in conjunctive normal form, 3 literals per clause): a b c d 0 0 0 0 0 Uf Output (a V b V c) · ( b V c V d) 1 In multi-valued logic, synthesis of a Grover oracle using Muthukrishnan-Stroud gates could potentially allow for a multi-valued extension of the SAT problem to represent greater numbers of parameters in search problems.

Yale talks about future applications of his work Time two minutes

In Summary Advantages of the Multi-Valued Deutsch-Jozsa Algorithm over Binary: - Analyzes multi-valued logical functions for constancy and affinity in O(1) time - Gives a deterministic output and provides an exponential speedup over classical algorithms Advantages of the Multi-Valued Grover Algorithm over Binary: -Greatly reduces memory register size (from lg N to log n N , a factor of about lg n ) -Greatly reduces the number of wasted information states -Requires less iterations and is hence more efficient for relatively small radices (conjecture)* -Enables quadratic speedup over classical search algorithms AND makes many NP problems tractable by solving more general search-related NP-complete problems *Ternary logic is optimal for quantum searching (conjecture)