############
###python###
############
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
def Half_Adder():
#Half Adder: inputs q0,q1 -> outputs q2=Sum, q3=Cout#
# Initialize local simulator
sim = AerSimulator()
# Quantum and Classical Registers
q = QuantumRegister(4, 'q') # q0=A, q1=B, q2=Sum, q3=Cout
c = ClassicalRegister(4, 'c')
qc = QuantumCircuit(q, c)
# Prepare inputs (using superposition as an example)
qc.h(q[0])
qc.h(q[1])
# Sum = A XOR B (Result stored in q2)
qc.cx(q[0], q[2])
qc.cx(q[1], q[2])
# Cout = A AND B (Using Toffoli gate -> result in q3)
qc.ccx(q[0], q[1], q[3])
# Measure all output and intermediate registers
qc.measure(q, c)
# Print ASCII circuit diagram
print("Half Adder Circuit (ASCII):")
print(qc.draw(output="text"))
# Execute simulation
result = sim.run(qc, shots=8192).result()
counts = result.get_counts()
print("\nHalf Adder Measurement Results:")
for k, v in sorted(counts.items()):
print(f"{k} : {v}")
def Full_Adder():
"""Full Adder: inputs q0(A), q1(B), q2(Cin) -> q3=Sum, q4=Cout"""
# Initialize local simulator
sim = AerSimulator()
# Quantum and Classical Registers
# q0=A, q1=B, q2=Cin, q3=Sum (acts as ancilla during calculation), q4=Cout
q = QuantumRegister(5, 'q')
c = ClassicalRegister(5, 'c')
qc = QuantumCircuit(q, c)
# Prepare inputs (using superposition as an example)
qc.h(q[0])
qc.h(q[1])
qc.h(q[2])
# --- Computational Flow (Maintaining Reversibility) ---
# 1) Calculate (A XOR B) and store in q3 (temporary)
qc.cx(q[0], q[3])
qc.cx(q[1], q[3])
# Now q3 = A XOR B
# 2) Calculate Cin AND (A XOR B), write result to q4 (Cout buffer)
qc.ccx(q[2], q[3], q[4])
# 3) Calculate (A AND B). If 1, flip q4.
# (Since both terms cannot be 1 simultaneously, XOR here acts as OR)
qc.ccx(q[0], q[1], q[4])
# Now q4 = (A AND B) OR (Cin AND (A XOR B)) -> Correct Carry Out (Cout)
# 4) Generate Sum: Add Cin to q3
# (q3 was A XOR B; after CX, it becomes A XOR B XOR Cin)
qc.cx(q[2], q[3])
# Now q3 = Sum
# Measure all registers
qc.measure(q, c)
# Print ASCII circuit diagram
print("\nFull Adder Circuit (ASCII):")
print(qc.draw(output="text"))
# Execute simulation
result = sim.run(qc, shots=8192).result()
counts = result.get_counts()
print("\nFull Adder Measurement Results:")
for k, v in sorted(counts.items()):
print(f"{k} : {v}")
'''
DFT： Y[k] = ∑{n=0~N-1} x[n] * exp(-j*2*π*n*k/N)
k — The frequency index in the frequency domain, k = 0, 1, 2, …, K−1.
n — The sample in the time domain and k fixed, n = 0, 1, 2, …, N−1.
N — The total number of sample.
x[n] — The time-domain signal. The raw data you have.
Y[k] — The frequency-domain signal. telling you how strong and what the phase is of the "frequency k"
component in the raw signal.
Angular frequency:
ω = 2πk / N
Real part + Imaginary part:
A·cos(ωn) + B·sin(ωn)
R = √(A² + B²) is Amplitude
θ = atan2(B, A) is Phase
Single sine wave + phase
R * cos(ωn + θ)
Real part + Imaginary part = Single sine wave + phase
when k=1:
n angle
0 0°
1 45°
2 90°
3 135°
when k=2:
n angle
0 0°
1 90°
2 180°
3 270°
Example:
Recording audio, fs = 8000 Hz, N = 8 samples:
k=0 → f = 0 × (8000/8) = 0 Hz (DC)
k=1 → f = 1 × (8000/8) = 1000 Hz
k=2 → f = 2 × (8000/8) = 2000 Hz
k=3 → f = 3 × (8000/8) = 3000 Hz
k=4 → f = 4 × (8000/8) = 4000 Hz
The DFT formula e^(+2πi·nk/N) has no idea what fs is.
It only computes "projections at k cycles" — the unit is cycles, not Hz.
QFT|x> = 1/sqrt(N) * ∑{k=0~N-1} exp(+2*π*i*x*k/N) * |k> #counter clockwise
3 qubits, N = 8
QFT|x⟩ = (1/√8) ·
[
k=0: e^(2πi·x·0/8) = e^0 = 1 · |000⟩
k=1: e^(2πi·x·1/8) = e^(2πi·x/8) · |001⟩
k=2: e^(2πi·x·2/8) = e^(2πi·x/4) · |010⟩
k=3: e^(2πi·x·3/8) = e^(2πi·3x/8) · |011⟩
k=4: e^(2πi·x·4/8) = e^(2πi·x/2) = e^(πi·x) · |100⟩
k=5: e^(2πi·x·5/8) = e^(2πi·5x/8) · |101⟩
k=6: e^(2πi·x·6/8) = e^(2πi·3x/4) · |110⟩
k=7: e^(2πi·x·7/8) = e^(2πi·7x/8) · |111⟩
]
Substitute formula example for x=5, N=8：
QFT|5> = (1/sqrt(8)) * ∑{k=0}^{8-1} [ e^(2*π*i*5*k/8) * |k> ]
QFT|5> = (1/√8) *
[
1 * |000>
+ (-√2/2-i√2/2) * |001>
+ i * |010>
+ ( √2/2-i√2/2) * |011>
+ (-1) * |100>
+ ( √2/2+i√2/2) * |101>
+ (-i) * |110>
+ (-√2/2+i√2/2) * |111>
]
All 8 states appeared evenly!
───────────────────────────────────
Known:
In circuit implementation, x must be expanded because the gate only recognizes qubits and not integers.
x = 4x₂ + 2x₁ + x₀ (x₂ = MSB, x₀ = LSB)
k = 4k₂ + 2k₁ + k₀ (k₂ = MSB, k₀ = LSB)
(binary expansion of k, k₂ = MSB, k₀ = LSB)
───────────────────────────────────
Step 1 substitute k into xk/8
xk/8 = x · (4k₂ + 2k₁ + k₀) / 8
xk/8 = (4xk₂ + 2xk₁ + xk₀) / 8
xk/8 = 4xk₂/8 + 2xk₁/8 + xk₀/8
xk/8 = xk₂/2 + xk₁/4 + xk₀/8
───────────────────────────────────
Step 2 expand the brackets
4x₂+2x₁+x₀ bring to Step 1
= (4x₂+2x₁+x₀)k₂/2 MSB
= (4x₂+2x₁+x₀)k₁/4 MID
= (4x₂+2x₁+x₀)k₀/8 LSB
───────────────────────────────────
Step 3 divide each term by 8 separately
MSB: (4x₂+2x₁+x₀)k₂/2
= 4x₂k₂/2 + 2x₁k₂/2 + x₀k₂/2
= 2x₂k₂ + x₁k₂ + x₀k₂/2
MID: (4x₂+2x₁+x₀)k₁/4
= 4x₂k₁/4 + 2x₁k₁/4 + x₀k₁/4
= x₂k₁ + x₁k₁/2 + x₀k₁/4
LSB: (4x₂+2x₁+x₀)k₀/8
= 4x₂k₀/8 + 2x₁k₀/8 + x₀k₀/8
= x₂k₀/2 + x₁k₀/4 + x₀k₀/8
───────────────────────────────────
Step 4 result
MSB: 2x₂k₂ and x₁k₂ are integers → drop
keep x₀k₂/2
MID: x₂k₁ is integer → drop
keep x₁k₁/2 + x₀k₁/4
LSB: no integers → keep all
keep x₂k₀/2 + x₁k₀/4 + x₀k₀/8
───────────────────────────────────
Step 5 split into 3 independent phases
MSB = e^(2πi · x₀k₂/2)
MID = e^(2πi · (x₁k₁/2 + x₀k₁/4))
LSB = e^(2πi · (x₂k₀/2 + x₁k₀/4 + x₀k₀/8))
───────────────────────────────────
Step 6 gate assignment
MSB: k₂=1 → e^(2πi·x₀/2)
MID: k₁=1 → e^(2πi·x₁/2)·e^(2πi·x₀/4)
LSB: k₀=1 → e^(2πi·x₂/2)·e^(2πi·x₁/4)·e^(2πi·x₀/8)
───────────────────────────────────
Each k bit is a qubit → value is ONLY 0 or 1
┌─────────────────────────┐
│ MSB │
│ e^(2πi · xk₂/2) │
│ │
│ k₂=0 → e^0 = 1 │ (no rotation, gate does nothing)
│ k₂=1 → e^(2πi·x/2) │ → H gate
└─────────────────────────┘
┌─────────────────────────┐
│ MID │
│ e^(2πi · xk₁/4) │
│ │
│ k₁=0 → e^0 = 1 │ (no rotation, gate does nothing)
│ k₁=1 → e^(2πi·x/4) │ → H + CP(π/2)
└─────────────────────────┘
┌─────────────────────────┐
│ LSB │
│ e^(2πi · xk₀/8) │
│ │
│ k₀=0 → e^0 = 1 │ (no rotation, gate does nothing)
│ k₀=1 → e^(2πi·x/8) │ → H + CP(π/2) + CP(π/4)
└─────────────────────────┘
───────────────────────────────────
Why is k called the "control"?
k is a qubit → only 0 or 1
k=0 → exponent = 0 → multiply by 1 → nothing happens
k=1 → exponent ≠ 0 → rotation activates → gate fires
This is exactly what a Controlled Phase gate does:
act only when the control qubit = 1, skip when = 0
───────────────────────────────────
'''
def Qft():
"""Quantum Fourier Transform (QFT) for 3 qubits"""
# Set up local simulator
sim = AerSimulator()
# Quantum and classical registers
q = QuantumRegister(3, 'q') # N = 2^(qubit number) = 8
c = ClassicalRegister(3, 'c')
qc = QuantumCircuit(q, c)
''''
Qiskit bit order => q[2] q[1] q[0]
1 0 1 = binary 101 input
Therefore x = 5
'''
qc.x(q[0]) #Flip 0→1
# q[1] No movement # q[1] Remains at 0
qc.x(q[2]) #Flip 0→1
# QFT
qc.h(q[0])
'''
theta = π/2 Phase rotation angle
control = q[1] Control qubit (determines whether to move)
target = q[0] Target qubit (the one being phase rotated)
'''
qc.cp(math.pi / 2.0, q[1], q[0]) # Controlled Phase gate CR2
qc.cp(math.pi / 4.0, q[2], q[0]) # Controlled Phase gate CR3
qc.h(q[1])
qc.cp(math.pi / 2.0, q[2], q[1]) # Controlled Phase gate CR2
qc.h(q[2])
# Bit reversal swap
qc.swap(q[0], q[2])
# Measurement
qc.measure(q, c)
# Print ASCII circuit diagram
print("QFT Circuit (ASCII):")
print(qc.draw(output="text"))
# Execute
result = sim.run(qc, shots=8192).result()
counts = result.get_counts()
print("\nQFT Measurement Results:")
for k, v in sorted(counts.items()):
print(f"{k} : {v}")
'''
DFT†: x[n] = (1/N) * ∑{k=0~N-1} Y[k] * exp(+2*pi*i*k*n/N)
QFT†: QFT†|k> = (1/N) * ∑{n=0~N-1} exp(-2*pi*i*k*n/N) |x> #clockwise
Reverse the order of all gates (because inverse reverses the operation order).
Negatively sign all angles in the Controlled-Phase.
The H gate and SWAP gate are their own inverses (no need to modify).
'''
def IQft():
"""Inverse Quantum Fourier Transform (IQFT) for 3 qubits"""
sim = AerSimulator()
q = QuantumRegister(3, 'q')
c = ClassicalRegister(3, 'c')
qc = QuantumCircuit(q, c)
# input: |101> = |5> the 5th frequency index in the frequency domain (k = 5).
qc.x(q[0])
# q[1] No movement # q[1] Remains at 0
qc.x(q[2])
# --- 直接做 IQFT ---
# Bit reversal swap at the beginning (QFT is placed at the end, IQFT is the opposite).
qc.swap(q[0], q[2])
# Negative values for both reverse and angle.
qc.h(q[2])
qc.cp(-math.pi / 2.0, q[2], q[1]) # CR2†
qc.h(q[1])
qc.cp(-math.pi / 4.0, q[2], q[0]) # CR3†
qc.cp(-math.pi / 2.0, q[1], q[0]) # CR2†
qc.h(q[0])
qc.measure(q, c)
print("IQFT Circuit (ASCII):")
print(qc.draw(output="text"))
result = sim.run(qc, shots=8192).result()
counts = result.get_counts()
print("\nIQFT Measurement Results:")
for k, v in sorted(counts.items()):
print(f"{k} : {v}")
'''
The core of Shor's algorithm: Quantum Phase Estimation (QPE)
1. Unitary:
Unitary is a quantum operation (gate) that never loses probability.
After the gate, the total probability is still 100%, and you can always reverse it back to the original state.
2. Eigenstate:
Eigenstate is a special quantum state that does not change its shape when a unitary gate U is applied to it.
It only gets an overall phase (a global rotation).
3. Phase Kickback:
Phase Kickback is the trick where the phase bounces back to the control qubit.
When you apply a controlled gate to an eigenstate, the phase does not stay on the target — it kicks back to the control qubit.
=============================================
RSA vs Shor's Algorithm - Clear Explanation
1. Classical RSA Key Generation (Public & Private Key)
Choose two prime numbers:
p = 61
q = 53
Compute modulus (public):
n = p * q = 61 * 53 = 3233
Compute Euler's totient function:
φ(n) = (p-1)*(q-1) = 60 * 52 = 3120
Choose public exponent e (coprime with φ(n)):
e = 17
Compute private exponent d:
d = 2753 (using extended Euclidean algorithm)
Encryption (anyone can do):
C = M^e mod n
Decryption (only who has d can do):
M = C^d mod n
=============================================
2. Classical Way to Break RSA (Trial Division)
To factor n = 3233:
Try dividing from 2, 3, 4, ..., until find divisor.
3233 ÷ 53 = 61 → Found p=61, q=53
This method is extremely slow for large n (e.g. 617-digit RSA-2048).
=============================================
3. Shor's Algorithm (Quantum Way) - Does NOT use φ(n)
Define the modular exponentiation function:
f(x) = a^x mod n
(example: a = 3, n = 3233)
Compute sequence:
3^0 mod 3233 = 1
3^1 mod 3233 = 3
3^2 mod 3233 = 9
...
3^260 mod 3233 = 1 ← returns to 1
Period r = 260
(means the function repeats every 260 steps)
=============================================
4. Quantum Core: Unitary Operator U
U |y⟩ = |a^y mod n⟩
This U is a Unitary operator (U†U = I)
Eigenvalue of U:
λ = e^(2πi φ)
where:
λ = eigenvalue
φ = phase (0 ≤ φ < 1) ← This is what QPE estimates
e = base of natural logarithm
2πi = complex phase factor
Relationship between phase and period:
φ = s / r
where:
r = period (260 in example)
s = integer, s = 0,1,2,...,r-1
=============================================
5. Role of QPE (Quantum Phase Estimation)
QPE estimates the phase φ ≈ s/r
Example: QPE may output φ ≈ 0.003846 (which is very close to 1/260)
Quantum computer finds possible φ values using superposition + QFT.
=============================================
6. From φ back to r (Continued Fraction Algorithm)
QPE gives approximate φ
→ Use Continued Fraction Expansion to find best fractions s/r
Example convergents:
0/1
1/259
1/260 ← Correct period found!
3/779
...
Then test candidate r values:
Check if a^r ≡ 1 mod n
If yes and r is even → proceed
=============================================
7. Final Step: Find p and q using r
r = 260 (even number)
Compute:
a^(r/2) = 3^130 mod 3233 = 794
Then:
gcd(a^(r/2) - 1, n) = gcd(794 - 1, 3233) = gcd(793, 3233) = 61 ← p
gcd(a^(r/2) + 1, n) = gcd(794 + 1, 3233) = gcd(795, 3233) = 53 ← q
n is successfully factored!
=============================================
Classical RSA:
Security depends on difficulty of factoring n into p and q
Needs φ(n) to compute private key d
Shor's Algorithm:
Finds the period r of a^x mod n using QPE
Estimates phase φ ≈ s/r
Uses Continued Fraction to recover r
Uses r to compute gcd and find p and q
Does NOT need φ(n)
Actual Shor initial inputs of the are:
a = 3 (fixed) Base, hard-coded in the circuit (like a fixed multiplier)
n = 3233 (fixed) Modulus, hard-coded in the circuit (all operations must be mod 3233)
U is U|y⟩ = |3^y mod 3233⟩ Core Unitary operation: y of 3^y mod 3233
x register |1⟩ initially contains 1 stores the value of y (result temporary register)
counting register |000⟩ initially 000 controls how many multiplications to perform.'''
def Qpe():
'''Quantum Phase Estimation (QPE) for a T gate'''
# Set up local simulator
sim = AerSimulator()
# 3 counting qubits and 1 target qubit
counting = QuantumRegister(3, 'counting')
target = QuantumRegister(1, 'target')
c = ClassicalRegister(3, 'c')
qc = QuantumCircuit(counting, target, c)
# 1. Initialization (flip target qubit to |1> to enable phase kickback)
qc.x(target[0])
# 2. Superposition
qc.h(counting)
# 3. Apply controlled-U gates, Unitary means satisfy U†U=I
# gate is equivalent to P(pi/4)
# When counting[0] = |1⟩, apply phase e^{i π/4} to target[0].
# Phase Kickback occurs, When counting[0] = |1⟩ counting[0] The phase e^{i π/4} is obtained by itself.
qc.cp(math.pi / 4.0, counting[0], target[0])
# gate is equivalent to P(pi/2)
# When counting[1] = |1⟩, apply phase e^{i π/2} to target[0].
# Phase Kickback occurs, When counting[1] = |1⟩, counting[1] The phase e^{i π/2} is obtained by itself.
qc.cp(math.pi / 2.0, counting[1], target[0])
#When counting[2] = |1⟩, apply a Z gate (phase e^{i π} = -1) to target[0].
#Phase Kickback occurs, When counting[2] = |1⟩, counting[2] acquires its own phase e^{i π} = -1.
qc.cz(counting[2], target[0])
# 4. Inverse Quantum Fourier Transform (Inverse QFT)
qc.swap(counting[0], counting[2])
qc.h(counting[0])
qc.cp(-math.pi / 2.0, counting[0], counting[1])
qc.h(counting[1])
qc.cp(-math.pi / 4.0, counting[0], counting[2])
qc.cp(-math.pi / 2.0, counting[1], counting[2])
qc.h(counting[2])
# 5. Measure counting qubits
qc.measure(counting, c)
# Print ASCII circuit diagram
print("QPE Circuit (ASCII):")
print(qc.draw(output="text"))
# Execute
result = sim.run(qc, shots=8192).result()
# result is The phase of U is φ = 1/8
counts = result.get_counts()
print("\nQPE Measurement Results:")
for k, v in sorted(counts.items()):
print(f"{k} : {v}")
if __name__ == "__main__":
Half_Adder()
Full_Adder()
Qft()
IQft()
Qpe()
#########
###c++###
#########
1. preinstall
sudo apt install -y build-essential wget libtinfo5 libstdc++-12-dev
wget --continue https://github.com/NVIDIA/cuda-quantum/releases/download/0.9.1/install_cuda_quantum_cu12.x86_64
chmod 755 ./install_cuda_quantum_cu12.x86_64
sudo ./install_cuda_quantum_cu12.x86_64 --accept --target /opt/nvidia/cuda-quantum
2. Makefile
TARGET = qpu_client
SRCDIR = ./source
OBJDIR = ./obj
BINDIR = ./bin
CXX = /opt/nvidia/cudaq/bin/nvq++
CXXFLAGS = -I/opt/nvidia/cudaq/include --target qpp-cpu -std=c++20 -fPIC -O0 -g
LDFLAGS = -L/opt/nvidia/cudaq/lib
CXXFILES = $(notdir $(wildcard $(SRCDIR)/*.cpp))
CXXOBJS = $(patsubst %.cpp, $(OBJDIR)/%.o, $(CXXFILES))
$(shell mkdir -p $(OBJDIR))
$(shell mkdir -p $(BINDIR))
$(OBJDIR)/%.o : $(SRCDIR)/%.cpp
$(CXX) -c $(CXXFLAGS) $< -o $@
$(TARGET): $(COBJS) $(CXXOBJS)
$(CXX) $^ $(LDFLAGS) -o $(BINDIR)/$@
all: $(TARGET)
clean:
rm -rf $(OBJDIR) $(BINDIR)
3. c++ source
__qpu__ static void half_adder() {
cudaq::qvector q(4);
h(q[0]);
h(q[1]);
// Sum
cx(q[0], q[2]);
cx(q[1], q[2]);
// Cout
ccx(q[0], q[1], q[3]);
mz(q);
}
__qpu__ static void qft() {
cudaq::qvector q(3);
// input：|101> = |5>
x(q[0]);
x(q[2]);
// QFT
h(q[0]);
r1(M_PI / 2.0, q[1], q[0]); // CR2
r1(M_PI / 4.0, q[2], q[0]); // CR3
h(q[1]);
r1(M_PI / 2.0, q[2], q[1]); // CR2
h(q[2]);
// Bit reversal swap
swap(q[0], q[2]);
mz(q);
}
__qpu__ static void iqft() {
cudaq::qvector q(3);
// input: |101> = |5>
x(q[0]);
x(q[2]);
// Bit reversal swap 放最前面
swap(q[0], q[2]);
// 反向、角度全部取負
h(q[2]);
r1(-M_PI / 2.0, q[2], q[1]); // CR2†
h(q[1]);
r1(-M_PI / 4.0, q[2], q[0]); // CR3†
r1(-M_PI / 2.0, q[1], q[0]); // CR2†
h(q[0]);
mz(q);
}
//The core of Shor's algorithm: Quantum Phase Estimation (QPE)
__qpu__ void qpe() {
cudaq::qvector counting(3);
cudaq::qubit target;
// 1. initialization
x(target);
// 2. superposition state
h(counting);
// 3. Apply a controlled U-gate <cudaq::ctrl>(control bits, target bits)
t<cudaq::ctrl>(counting[0], target);
s<cudaq::ctrl>(counting[1], target);
// 4. The Z gate can be directly implemented using the built-in cz, or z<cudaq::ctrl>.
cz(counting[2], target);
// 5.Inverse Quantum Fourier Transform (Inverse QFT)
swap(counting[0], counting[2]);
h(counting[0]);
// r1 parameter order is (angle, qubit).
// The controlled version is (angle, control bits, target bits).
r1<cudaq::ctrl>(-M_PI / 2.0, counting[1], counting[0]);
h(counting[1]);
r1<cudaq::ctrl>(-M_PI / 4.0, counting[2], counting[0]);
r1<cudaq::ctrl>(-M_PI / 2.0, counting[2], counting[1]);
h(counting[2]);
// 5. Measure
mz(counting);
}
int main() {
int shots = 8192;
cudaq::sample_result counts00 = cudaq::sample(shots, half_adder);
cudaq::sample_result counts01 = cudaq::sample(shots, qft);
cudaq::sample_result counts02 = cudaq::sample(shots, iqft);
cudaq::sample_result counts03 = cudaq::sample(shots, Qpe);
// Output result
std::cout << "CUDA-Q Half Adder Results:\n";
for(auto& [bits, count] : counts00) {
std::cout << bits << " : " << count << "\n";
}
std::cout << "\nQft Results:\n";
for(auto& [bits, count] : counts01) {
std::cout << bits << " : " << count << "\n";
}
std::cout << "\nIQft Results:\n";
for(auto& [bits, count] : counts02) {
std::cout << bits << " : " << count << "\n";
}
std::cout << "\nQpe_Gate Results:\n";
for (auto& [bits, count] : counts03) {
std::string reversed_bits = bits;
// Reverse a string using the C++ standard library
std::reverse(reversed_bits.begin(), reversed_bits.end());
std::cout << "Reversed Binary [" << reversed_bits << "] : " << count << " times" << std::endl;
}
return 0;
}
4. debug
sudo apt install nvidia-cuda-gdb
/usr/bin/cuda-gdb /root/asustor_projects/qpu_client/bin/qpu_client
(cuda-gdb): directory /root/asustor_projects/qpu_client/source
(cuda-gdb): set solib-absolute-prefix /opt/nvidia/cudaq
(cuda-gdb): set solib-search-path /opt/nvidia/cudaq/lib:/opt/nvidia/cudaq/lib64
(cuda-gdb): break qpu_client.cpp:21
(cuda-gdb): run
=============================================
Appendix: Dilithium algorithm defense Shor's algorithm
Dilithium algorithm theory:
1. Key Generation (with error)
Public modulus q = 23
Public parameter A = 5
Secret private key s = 3
Gaussian error e = 1 (the core of lattice obfuscation: error, not natural exponent)
Gaussian normal distribution y = [1 / (σ * √(2π))] * e^[-(x-μ)² / 2σ²] | where x is the error
1. Horizontal shift (μ): center point. Dilithium sets μ = 0.
2. Width scaling (σ): standard deviation. Determines the "diffusion degree" of the error.
3. When μ = 0, σ = 1, x = 1: y = 0.242 probability density
Compute public key t:
t = (A * s + e) mod q
= (5 * 3 + 1) mod 23
= 16 mod 23
= 16
Public key content: (A = 5, t = 16)
Secret key content: (s = 3)
----------------------------------------------------------
2. Signing
Select random mask y = 7
Compute intermediate value w:
w = (A * y) mod q
= (5 * 7) mod 23
= 35 mod 23
= 12
[Extract high bits of the restored value] Set divisor d = 8 (lattice size):
w_high = floor(12 / 8) = floor(1.5) = 1
Compute challenge value c (hash):
c = Hash(message, w_high) = Hash(message, 1)
Assume c = 2
Compute signature value z:
z = (y + c * s) mod q = (7 + 2 * 3) mod 23 = 13
Signature output: (z = 13, c = 2)
----------------------------------------------------------
3. Verification
The verifier only knows public parameters A=5, t=16 and signature z=13, c=2
Compute A * z mod q:
= 5 * 13 mod 23 = 65 mod 23 = 19
Compute c * t mod q:
= 2 * 16 mod 23 = 32 mod 23 = 9
Restore intermediate value w':
w' = (A * z - c * t) mod q
= (19 - 9) mod 23
= 10
[Extract high bits of the restored value] Use the same divisor d = 8 (lattice size):
w'_high = floor(10 / 8) = floor(1.25) = 1
Recompute challenge value c':
c' = Hash(message, w'_high) = Hash(message, 1) = 2
Verification result: c' == c (2 == 2), signature is valid!
----------------------------------------------------------
4. Mathematical Equation Verification
Here we substitute the definitions of z and t to prove the relationship between w' and w:
w' = (A * z - c * t) mod q
Substitute z = (y + c s) mod q and t = (A s + e) mod q:
w' = (A * [(y + c s) mod q] - c * [(A s + e) mod q]) mod q
According to modular arithmetic properties [(a mod q) = a] inside the brackets, it can be simplified as:
w' = (A * (y + c s) - c * (A s + e)) mod q
Expand the brackets:
w' = (A y + A c s - c A s - c e) mod q
The terms A c s and c A s cancel out (because A c s - c A s = 0):
w' = (A y - c e) mod q
Since (A y) mod q = w, it is proven that:
w' = (w - c e) mod q
Numerical verification:
w' = (12 - 2 * 1) mod 23
= 10 mod 23
= 10 (consistent with the result in step 3)
----------------------------------------------------------
5. Handling of Lattice Obfuscation (HighBits Concept)
In Dilithium, as long as the error c e is within the allowable range, it does not affect verification.
We compare the "high bits (HighBits)":
Definition HighBits(x) = floor(x / 8) (lattice size = 8)
HighBits(w) = floor(12 / 8) = 1
HighBits(w') = floor(10 / 8) = 1
Result: HighBits(w) == HighBits(w'), signature is valid!
This is how the "lattice grid" tolerates lattice obfuscation (error e).
Once we introduce the error e, the originally perfect mathematical equation becomes the LWE (Learning With Errors) problem.
Without e (quantum computer breaks it instantly):
Quantum computers (or even ordinary computers) can use Shor's algorithm on t = A * s mod q, which is a set of linear equations.
With e (quantum computer gets stuck):
t = A * s + e mod q. At this point, t no longer falls perfectly on multiples of A, but is randomly offset by a small amount.
1. No exponential structure: t = A * s + e is a linear combination plus noise. It does not keep flipping and returning to 1 like a^x.
2. No periodicity to follow: Because e is randomly chosen (usually following a discrete Gaussian distribution), it has no regular regression pattern like x=0, 1, 2...
This toy example illustrates how Dilithium uses lattice-based cryptography with errors to achieve post-quantum security.
refer to: https://github.com/Transia-RnD/rippled/tree/dilithium-full
~/src/libxrpl/protocol/SecretKey.cpp
std::pair<PublicKey, SecretKey>
generateKeyPair(KeyType type, Seed const& seed)
{
switch (type)
{
case KeyType::secp256k1: {
detail::Generator g(seed);
return g(0);
}
case KeyType::ed25519: {
auto const sk = generateSecretKey(type, seed);
return {derivePublicKey(type, sk), sk};
}
case KeyType::dilithium: {
auto const sk = generateSecretKey(type, seed);
return {derivePublicKey(type, sk), sk};
}
default:
throw std::invalid_argument("Unsupported key type");
}
}
download:
https://www.mediafire.com/file/3z8e1hi2r752k59/qft.pptx/file
https://www.mediafire.com/file/v7f1zyfilbdqekl/qpu_py.tar.xz/file
https://www.mediafire.com/file/xkzvn6odzf1orq6/qpu_client.tar.xz/file
ps:
my thoughts that qiskit and cuda-q ideas of "using software to
design hardware circuits" is very similar to RISC-V's Scala. Qiskit
(Python) = a quantum version of "Hardware Description Language (HDL)".
沒有留言:
張貼留言