Assume a basic N-bit Classical RISC processor (each processor register is N bits). How its insruction set would need to change for it to become an N-bit Quantum RISC processor?
Actually most of the instructions would not need any change. For example, arithmetic and logic instructions would still be the same, but they would process qubit states (0,1,U) instead of bit states (0,1).
Maybe just load/store instruction(s) need to be modified (from a programmer point of view):
Assume that, if a LOAD instruction for a basic N-bit Classical RISC processor is:
LOAD Ri, 'a literal string of N 0/1'
Then the LOAD instruction for N-bit Quantum RISC processor would be:
LOAD Ri, 'a literal string of N 0/1/U' (U for Unknown/Undetermined states)
Quantum algorithm examples for such a N-bit Quantum RISC processor:
Quantum Integer Factorization Algorithm:
Problem: Assume A*B=C; A and B are known to be prime numbers; the value of C is given. What are the values of A and B?
LOAD R0, 'U'*N # 'U'*N: a literal string of N 'U's
LOAD R1, 'U'*N # 'U'*N: a literal string of N 'U's
MULT R0, R1, R2 # R0*R1 -> R2
LOAD R2, C # => A -> R0 and B -> R1 after this instruction! (C is N-digit binary (as literal string) value.)
Imagine that, when R2 is forced to have the value of C in the end, that causes states of R0 and R1 change from unknown to real values of A and B, thus solving the problem.
Quantum First Degree Polynomial Equation Solving Algorithm:
Problem: Assume A*X+B=0. What is X if A and B are given? (Analytical solution: X=-B/A)
LOAD R0, 'U'*N # 'U'*N: a literal string of N 'U's
LOAD R1, A # A is N-digit binary (as literal string) value
LOAD R2, B # B is N-digit binary (as literal string) value
MULT R0, R1, R3 # R0*R1 -> R3
ADDN R2, R3, R3 # R2+R3 -> R3
LOAD R3, '0'*N # => X -> R0 after this instruction (which is the solution)!
Quantum Second Degree Polynomial Equation Solving Algorithm:
Problem: Assume A*X*X+B*X+C=0. What is X if A and B and C are given? (Analytical solution: Quadratic formula!)
LOAD R0, 'U'*N # 'U'*N: a literal string of N 'U's
LOAD R1, A # A is N-digit binary (as literal string) value
LOAD R2, B # B is N-digit binary (as literal string) value
LOAD R3, C # C is N-digit binary (as literal string) value
MULT R0, R0, R4 # R0*R0 -> R4
MULT R1, R4, R4 # R1*R4 -> R4
MULT R0, R2, R5 # R0*R2 -> R5
ADDN R4, R5, R4 # R4+R5 -> R4
ADDN R4, R3, R4 # R4+R3 -> R4
LOAD R4, '0'*N # => X0 or X1 (with %50 probability for each) -> R0 after this instruction (which is the solution)!
Quantum Second Degree Polynomial Equation Solving Algorithm 2:
Problem: Assume A*X*X+B*X+C=0. X0+X1=-B/A & X0*X1=C/A. What is X if A and B and C are given? (Analytical solution: Quadratic formula!)
LOAD R0, 'U'*N # 'U'*N: a literal string of N 'U's
LOAD R1, 'U'*N # 'U'*N: a literal string of N 'U's
ADDN R0, R1, R2 # R0+R1 -> R2
MULT R0, R1, R3 # R0*R1 -> R3
LOAD R2, -B/A # as N-digit binary (as literal string) value
LOAD R3, C/A # as N-digit binary (as literal string) value
=> X0 -> R0 and X1 -> R1 after these (which is the solution)!
Realize that such a N-bit Quantum RISC processor could also still work as a N-bit Classical RISC processor (by simply never setting any register qubits to unknown states)! Meaning, a quantum computer has at least the same power as a classical computer for any/all worst problem cases! Meaning, finding even a single problem that a quantum computer can solve faster, would mean a proof of quantum supremacy! And realize that the Quantum Integer Factorization Algorithm above uses only 4 instructions! Could there be any chance that the N-bit Classical RISC processor (which has the same instruction set as the N-bit Quantum RISC processor), could solve the same problem using an equal or less number of instructions? The answer is obviously no, which means we have a proof of quantum supremacy!
What are the advantages of quantum computers against classical computers, in general?
Realize that the Quantum Integer Factorization Algorithm above evaluates (in the end) all possible values of A and B instantly to find the (unique) solution.
(Imagine that whenever a problem has multiple possible solutions then a quantum computer randomly picks one each time.)
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.