Full text
Quantum Circuit Specification for QADK Overview This document provides the complete quantum circuit specification for implementing QADK (Quantum-Annealed Discriminative Kernel) on quantum hardware. The specification includes: 1. Feature Map Circuit: Gate-level design for encoding classical data into quantum states 2. Swap-Test Circuit: Procedure for estimating quantum fidelity |���|���|² 3. Shot Noise Analysis: Measurement precision requirements and statistical analysis 4. End-to-End Complexity: Resource requirements and time estimates for full kernel computation 5. NISQ Feasibility: Assessment of implementability on current quantum hardware 1. Feature Map Circuit 1.1 Qubit Count and Hilbert Space Dimension Qubit Count:n_qubits = ceil(log2(embedding_dim)) For the standard QADK configuration: - embedding_dim = 32 →n_qubits = 5 -embedding_dim = 64 →n_qubits = 6 -embedding_dim = 128 →n_qubits = 7 Hilbert Space Dimension:2^n_qubits - For n_qubits = 5: Hilbert_dim = 32 - For n_qubits = 6: Hilbert_dim = 64 - For n_qubits = 7: Hilbert_dim = 128 1.2 Circuit Structure The feature map circuit prepares quantum state |�(x)� from classical input vector x: Circuit Structure: ��� Initialization: |0�^�n_qubits ��� Amplitude Encoding Layer � ��� RY(�_0) on q_0 � ��� RY(�_1) on q_1 � ��� ... � ��� RY(�_{n_qubits-1}) on q_{n_qubits-1} ��� Phase Encoding Layer � ��� RZ(�_0) on q_0 � ��� RZ(�_1) on q_1 1
� ��� ... � ��� RZ(�_{n_qubits-1}) on q_{n_qubits-1} ��� Entangling Layers (repeat depth times) ��� Entangling Layer � ��� CZ(q_0, q_1) � ��� CZ(q_1, q_2) � ��� ... � ��� CZ(q_{n_qubits-2}, q_{n_qubits-1}) ��� Parameterized Rotations ��� RY(�_i^l) on each qubit ��� RZ(�_i^l) on each qubit 1.3 Gate-Level Description Initialization •State: |0�^�n_qubits (all qubits initialized to |0�) Amplitude Encoding (First Layer) •Gates:RY(�_i) for i = 0, …, n_qubits-1 •Parameters: –�_i = arcsin(x_norm[i]) where x_norm is normalized input –Maps ||x|| to global amplitude modulation •Gate Count: n_qubits RY gates Phase Encoding (First Layer) •Gates:RZ(�_i) for i = 0, …, n_qubits-1 •Parameters: –�_i = 2� * Σ_j W_ij * x[j] –W is random Gaussian projection matrix (n_qubits × n_features) –W_ij ~ N(0, 1) •Gate Count: n_qubits RZ gates Entangling Layers (Depth = 2) Each layer consists of: 1. CZ Gates (Linear Connectivity): •CZ(q_i, q_{i+1}) for i = 0, …, n_qubits-2 • Gate Count per layer: n_qubits - 1 2. Parameterized Rotations: •RY(�_i^l) on each qubit (layer l) •RZ(�_i^l) on each qubit (layer l) • Gate Count per layer: 2 * n_qubits Total Gates per Entangling Layer: (n_qubits - 1) + 2 * n_qubits = 3 * n_qubits - 1 2
1.4 Gate Count and Circuit Depth For embedding_dim = 32, n_qubits = 5, depth = 2: •Encoding Gates: 2 * n_qubits = 10 gates (5 RY + 5 RZ) •Entangling Layers: depth * (3 * n_qubits - 1) = 2 * 14 = 28 gates •Total Gates: 10 + 28 = 38 gates per feature map Circuit Depth: - Encoding: 2 layers (1 for amplitude, 1 for phase) - Entangling: 2 * 3 = 6 layers (each layer has CZ + rotations) - Total Depth: ~6 layers Connectivity: Linear (adjacent qubits only) 1.5 Gate Types Used •RY(�): Rotation around Y-axis by angle � •RZ(�): Rotation around Z-axis by angle � •CZ: Controlled-Z gate (entangling gate) 1.6 State Preparation Procedure For a classical input vector x � �^n_features: 1. Normalize input: x_norm = x / ||x|| 2. Prepare |0�^�n_qubits 3. Apply amplitude encoding: RY(�_i) where �_i = arcsin(x_norm[i]) 4. Apply phase encoding: RZ(�_i) where �_i = 2� * (W @ x)[i] 5. Apply entangling layers (depth times): • Apply CZ gates between adjacent qubits • Apply parameterized RY and RZ rotations 6. Final state: |�(x)� in 2^n_qubits-dimensional Hilbert space 2. Swap-Test Circuit for Fidelity Estimation 2.1 Purpose The swap-test circuit estimates quantum fidelity: F(��, ��) = |���|���|² This is the squared overlap between two quantum states, which is used as the fidelity term in the QADK kernel. 2.2 Qubit Allocation Total Qubits Required:2 * n_qubits + 1 •Ancilla qubit: 1 qubit (q_0) - control qubit for swap operation •State 1: n_qubits qubits (q_1 … q_n_qubits) - first quantum state |��� 3
•State 2: n_qubits qubits (q_{n_qubits+1} … q_{2*n_qubits}) - second quantum state |��� For n_qubits = 5 (embedding_dim = 32): - Total Qubits:2*5+1=11 qubits - Ancilla: q_0 - State 1: q_1, q_2, q_3, q_4, q_5 - State 2: q_6, q_7, q_8, q_9, q_10 2.3 Circuit Layout Qubit Layout: ��������������������������������������������������������� � Ancilla � State 1 � State 2 � � q_0 � q_1 ... q_5 � q_6 ... q_10 � ��������������������������������������������������������� 2.4 Gate-Level Circuit Description Step-by-Step Procedure: 1. State Preparation: • Prepare |��� on qubits q_1 … q_n_qubits using feature map circuit above • Prepare |��� on qubits q_{n_qubits+1} … q_{2*n_qubits} using feature map circuit above • Initialize ancilla: |0� on q_0 2. Hadamard on Ancilla: •H(q_0) → (|0� + |1�)/√2 3. Controlled-SWAP Operations: • For i = 1 to n_qubits: –CSWAP(q_0, q_i, q_{i+n_qubits}) –Conditionally swaps qubits from State 1 and State 2 when ancilla is |1� 4. Hadamard on Ancilla (again): •H(q_0) → Projects ancilla to |0� or |1� 5. Measurement: • Measure q_0 • Result: 0 or 1 2.5 Gate Count For n_qubits = 5: •Hadamard gates: 2 (before and after CSWAP) •CSWAP gates: n_qubits = 5 •Total Gates:2+5=7 gates Circuit Depth: ~3 layers (H → CSWAP → H) 4
2.6 Fidelity Estimation Formula Measurement Probability: - P(q_0 = 0) = (1 + F) / 2 - P(q_0 = 1) = (1 -F)/2 Fidelity Calculation: - F = |���|���|² = 2 * P(q_0 = 0) - 1 Example: - If we measure 0 with probability 0.9: F = 2 * 0.9 - 1 = 0.8 - If we measure 0 with probability 0.5: F = 2 * 0.5 - 1 = 0.0 2.7 Mathematical Foundation The swap-test circuit implements the following operation: |0� � |��� � |��� → [|0� � (|��� � |��� + |��� � |���) + |1� � (|��� � |��� - |��� � |���)] / 2 After Hadamard and measurement: - Probability of measuring |0�: (1 + |���|���|²) / 2 - Therefore: F = |���|���|² = 2 * P(0) - 1 3. Shot Noise Analysis 3.1 Problem Statement Quantum measurements are probabilistic. To estimate fidelity F with precision �, we need multiple measurement shots. Shot noise arises from the binomial sampling nature of quantum measurements. 3.2 Shot Budget Calculation Target Precision: � (e.g., 0.01 = 1% precision) Confidence Level: Typically 95% (z = 1.96) or 99% (z = 2.576) Variance Analysis: - Measurement probability: p = P(q_0 = 0) = (1 + F) / 2 - Binomial variance: �²_p = p(1-p) / n_shots - Worst case (F = 0): p = 0.5, variance is maximal - Fidelity variance: �²_F = 4 * �²_p (since F = 2p - 1) Required Shots: n_shots = (z * 2 * �_p_max / �)² =(z*2*0.5/�)² = (z / �)² For 95% confidence (z = 1.96) and 1% precision (� = 0.01): - n_shots = (1.96 / 0.01)² = 38,416 shots 3.3 Shot Requirements for Different Scenarios 5
Precision Confidence Z-Score Shots Required 1% (0.01) 95% 1.96 38,416 1% (0.01) 99% 2.576 66,337 0.5% (0.005) 95% 1.96 153,664 2% (0.02) 95% 1.96 9,604 Standard Configuration:38,416 shots for 1% precision at 95% confidence 3.4 Shot Noise Simulation Method: Binomial sampling simulation For true fidelity F_true and n_shots measurements: 1. True measurement probability: p_zero = (1 + F_true) / 2 2. Simulate n_shots measurements: n_zeros ~ Binomial(n_shots, p_zero) 3. Estimated probability: p_estimated = n_zeros / n_shots 4. Estimated fidelity: F_estimated = 2 * p_estimated - 1 5. Repeat for n_experiments to get statistics Example Results (F_true = 0.8, n_shots = 38,416): Statistic Value True Fidelity 0.8000 Mean Estimated 0.8000 Std Estimated 0.0030 Bias 0.0000 RMSE 0.0030 Min 0.7895 Max 0.8086 Interpretation: - Unbiased estimator (bias � 0) - Standard deviation � 0.003 (within target precision) - 95% of estimates fall within ±0.006 of true value 3.5 Precision vs. Shots Trade-off Relationship:n_shots � 1 / �² To double precision (halve �), need 4× more shots: - 1% precision: 38,416 shots - 0.5% precision: 153,664 shots (4×) Practical Recommendation: - For initial experiments: 1% precision (38,416 shots) - For final results: 0.5% precision (153,664 shots) if needed 6
4. End-to-End Complexity Analysis 4.1 Problem Setup Task: Compute full QADK kernel matrix K for n_samples data points For Standard Configuration: - n_samples = 1,000 (typical ECG dataset size) - embedding_dim = 32 (standard QADK configuration) - n_qubits = 5 (ceil(log2(32))) Kernel Matrix Size: n_samples × n_samples = 1,000 × 1,000 Kernel Entries: n_samples × (n_samples + 1) / 2 = 500,500 unique pairs (symmetric matrix) 4.2 Resource Requirements per Kernel Entry Feature Map Circuits: - 2 circuits needed (one for each data point) - Gates per feature map: 38 gates - Total feature map gates: 2 × 38 = 76 gates Swap-Test Circuit: - 1 circuit per kernel entry - Gates: 7 gates - Total gates per entry: 76 + 7 = 83 gates Qubits Required: - Per kernel entry: 11 qubits (2 × 5 + 1) - Maximum simultaneous: 11 qubits (can reuse for sequential computation) Shots Required: - Per kernel entry: 38,416 shots (for 1% precision) - Total shots per entry: 38,416 4.3 Total Resource Requirements Total Gates: - 500,500 kernel entries × 83 gates = 41,541,500 gates Total Shots: - 500,500 kernel entries × 38,416 shots = 19,227,208,000 shots Memory Requirements: - State preparation: O(2^n_qubits) = O(32) per state - Measurement storage: O(n_shots) = O(38,416) per entry - Kernel storage: O(n_samples²) = O(1,000,000) complex numbers 4.4 Time Estimates Assumptions: - Gate time: ~50 ns per gate (typical NISQ device) - Measurement time: ~1 �s per shot (typical NISQ device) - Circuit reset time: ~1 �s (negligible compared to measurements) Per Kernel Entry: 1. Circuit Execution Time: • 83 gates × 50 ns = 4.15 �s 2. Measurement Time: • 38,416 shots × 1 �s = 38.416 ms 3. Total Time per Entry: 7
• 4.15 �s + 38.416 ms � 38.42 ms (measurement-limited) Total Time: - 500,500 entries × 38.42 ms = 19,229 seconds � 5.34 hours Bottleneck: Shot noise dominates computation time (99.99% of time is measurement) 4.5 Parallelization Potential Parallelizable: Each kernel entry can be computed independently Limitations: - Limited qubits per device (e.g., 127 qubits max) - Can compute at most ~11 kernel entries simultaneously on one device - Would need multiple devices or time-multiplexing With Full Parallelization (assuming unlimited devices): - Minimum time: Single entry time = 38.42 ms - Still measurement-limited, not gate-limited 4.6 Comparison with Classical Implementation Classical Implementation (current QADK): - Complexity: O(n² × m) = 1,000² × 32 = 32,000,000 operations - Time: ~32 ms (at 1 GFLOPS) or ~3.2 ms (at 10 GFLOPS) - Accuracy: Exact (no shot noise) Quantum Implementation (hypothetical): - Time: ~5.34 hours (sequential) or ~38 ms (fully parallel) - Accuracy: ±0.01 precision (shot noise limited) - Hardware: Requires NISQ device access Speedup Analysis: - Sequential: Classical is ~10,000× faster than quantum - Parallel: Quantum could be ~3× slower than classical (at best) - Verdict: Classical implementation is more efficient for current problem sizes Quantum Advantage Region: Only when embedding_dim » 1000 (requiring 10+ qubits per state), where classical simulation becomes intractable. 5. NISQ Feasibility Assessment 5.1 Device Specifications Current NISQ Device (IBM Eagle-like): - Available Qubits: 127 - Gate Fidelity: 0.999 (~0.1% error per gate) - Coherence Time: 100 �s (T2) - Gate Time: ~50 ns per gate - Measurement Rate: ~1 MHz 5.2 Feasibility Checks Check 1: Qubit Count •Required: 11 qubits (for swap-test with n_qubits=5) •Available: 127 qubits •Status: � FEASIBLE (11 « 127) 8
Check 2: Coherence Time •Circuit Duration: 83 gates × 50 ns = 4.15 �s •T2 Coherence Time: 100 �s •Ratio: 4.15 �s / 100 �s = 4.15% •Status: � FEASIBLE (well within coherence window) Check 3: Circuit Fidelity •Gates per Entry: 83 gates •Gate Fidelity: 0.999 •Expected Circuit Fidelity: 0.999^83 � 0.920 •Threshold: > 0.5 for useful computation •Status: � FEASIBLE (0.920 > 0.5) 5.3 Overall Feasibility Assessment All Checks Pass: � TECHNICALLY FEASIBLE on current NISQ hardware Qualification: - Feasible from a hardware perspective - Practical limitations due to: 1. Shot noise: Requires ~38k shots per entry 2. Time cost: 5+ hours for full kernel matrix 3. Device access: Limited availability of NISQ devices 4. Classical alternative: Much faster and more accurate for current problem sizes 5.4 Practical Recommendations For Current Problem Sizes (n_samples � 1,000, embedding_dim � 64): - � Use classical implementation (more efficient) - � Quantum implementation not recommended (slower, less accurate, requires hardware access) For Future Large-Scale Problems (n_samples » 10,000, embedding_dim » 1,000): - � Quantum implementation may become advantageous - � Classical simulation becomes intractable - � Quantum speedup could emerge For Proof-of-Concept (small subset of data): - � Quantum implementation feasible for validation - � Could demonstrate quantum advantage on specific sub-problems - � Useful for research purposes 6. Mapping to Classical Implementation 6.1 Theoretical Quantum Circuit → Classical Approximation Quantum Circuit Output: - State: |�(x)� prepared via feature map circuit - Fidelity: F = |���|���|² measured via swap-test with shot noise 9
