In [4]:
import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit.quantum_info import SparsePauliOp
try:
from qiskit_aer.primitives import EstimatorV2
except ImportError:
from qiskit.primitives import EstimatorV2
from qiskit_aer import AerSimulator
from scipy.optimize import minimize
data = [64, 34, 25, 520, 23, 12, 22, 11, 90, 88]
n = len(data)
current_data = data.copy()
pass_num = 0
max_passes = 50 # Prevent infinite loop
print(f"Original data: {data}")
print(f"Target: {sorted(data)}\n")
def circuit_for_pass(current_data, p=1):
n_qubits = len(current_data) - 1
qc = QuantumCircuit(n_qubits)
# Hadamard on all qubits
for i in range(n_qubits):
qc.h(i)
params_gamma = [Parameter(f"γ_{layer}") for layer in range(p)]
params_beta = [Parameter(f"β_{layer}") for layer in range(p)]
for layer in range(p):
# Cost layer - for each neighbor comparison
for i in range(n_qubits - 1):
qc.cx(i, i + 1)
qc.rz(2 * params_gamma[layer], i + 1)
qc.cx(i, i + 1)
# Mixer layer
for i in range(n_qubits):
qc.rx(2 * params_beta[layer], i)
return qc, params_gamma, params_beta
def create_cost_hamiltonian(current_data):
n_qubits = len(current_data) - 1
pauli_list = []
for i in range(n_qubits):
pauli_str = ["I"] * n_qubits
pauli_str[i] = "Z"
pauli_str = "".join(pauli_str)
# If element is greater than next, we want qubit = 1
if current_data[i] > current_data[i + 1]:
pauli_list.append((pauli_str, 1.0))
else:
pauli_list.append((pauli_str, -1.0))
return SparsePauliOp.from_list(pauli_list)
def optimize_circuit(current_data):
n_qubits = len(current_data) - 1
ansatz, params_gamma, params_beta = circuit_for_pass(current_data, p=1)
all_params = params_gamma + params_beta
cost_hamiltonian = create_cost_hamiltonian(current_data)
estimator = EstimatorV2()
def evaluate_energy(parameters):
try:
job = estimator.run(ansatz, cost_hamiltonian, parameter_values=parameters)
result = job.result()
return float(np.real(result.values[0]))
except:
return 1e10
x0 = np.random.random(len(all_params)) * np.pi
result = minimize(evaluate_energy, x0, method="L-BFGS-B", options={"maxiter": 200})
final_circuit = ansatz.copy()
param_dict = {param: val for param, val in zip(all_params, result.x)}
final_circuit = final_circuit.assign_parameters(param_dict)
final_circuit.measure_all()
simulator = AerSimulator()
job = simulator.run(final_circuit, shots=500)
counts = job.result().get_counts()
# Most frequent bitstring
best_bitstring = max(counts.items(), key=lambda x: x[1])[0]
return best_bitstring
def is_sorted(data):
"""Check if data is sorted - iterate left to right"""
for i in range(len(data) - 1):
if data[i] > data[i + 1]:
# Found two neighboring elements in wrong order
return False
# All neighboring pairs are in order
return True
while not is_sorted(current_data) and pass_num < max_passes:
pass_num += 1
print(f"\nPASS: {pass_num}")
print(f"Current: {current_data}")
bitstring = optimize_circuit(current_data)
print(f"Bitstring: {bitstring}")
# Perform swaps based on bitstring
swaps = 0
for i in range(len(current_data) - 1):
bit = int(bitstring[::-1][i])
if bit == 1 and current_data[i] > current_data[i + 1]:
# Correct comparison - should swap
current_data[i], current_data[i + 1] = current_data[i + 1], current_data[i]
swaps += 1
print(f" Swap {i},{i+1}: {current_data[i+1]} <-> {current_data[i]}")
elif bit == 0 and current_data[i] <= current_data[i + 1]:
# Correct comparison - don't swap
pass
else:
# Incorrect comparison
pass
print(f"Performed {swaps} swaps")
print("\n\n")
print(f" Final: {current_data}")
print(f" Passes: {pass_num}")
if is_sorted(current_data):
print("\nSUCCESS! Data is sorted!")
else:
print(f"\nFailed to sort in {max_passes} passes")
Original data: [64, 34, 25, 520, 23, 12, 22, 11, 90, 88] Target: [11, 12, 22, 23, 25, 34, 64, 88, 90, 520] PASS: 1 Current: [64, 34, 25, 520, 23, 12, 22, 11, 90, 88] Bitstring: 000111100 Swap 3,4: 520 <-> 23 Swap 4,5: 520 <-> 12 Swap 5,6: 520 <-> 22 Performed 3 swaps PASS: 2 Current: [64, 34, 25, 23, 12, 22, 520, 11, 90, 88] Bitstring: 011010101 Swap 0,1: 64 <-> 34 Swap 2,3: 25 <-> 23 Swap 6,7: 520 <-> 11 Swap 7,8: 520 <-> 90 Performed 4 swaps PASS: 3 Current: [34, 64, 23, 25, 12, 22, 11, 90, 520, 88] Bitstring: 001101011 Swap 1,2: 64 <-> 23 Swap 3,4: 25 <-> 12 Swap 5,6: 22 <-> 11 Performed 3 swaps PASS: 4 Current: [34, 23, 64, 12, 25, 11, 22, 90, 520, 88] Bitstring: 001010100 Swap 2,3: 64 <-> 12 Swap 4,5: 25 <-> 11 Performed 2 swaps PASS: 5 Current: [34, 23, 12, 64, 11, 25, 22, 90, 520, 88] Bitstring: 100111100 Swap 3,4: 64 <-> 11 Swap 4,5: 64 <-> 25 Swap 5,6: 64 <-> 22 Swap 8,9: 520 <-> 88 Performed 4 swaps PASS: 6 Current: [34, 23, 12, 11, 25, 22, 64, 90, 88, 520] Bitstring: 111111111 Swap 0,1: 34 <-> 23 Swap 1,2: 34 <-> 12 Swap 2,3: 34 <-> 11 Swap 3,4: 34 <-> 25 Swap 4,5: 34 <-> 22 Swap 7,8: 90 <-> 88 Performed 6 swaps PASS: 7 Current: [23, 12, 11, 25, 22, 34, 64, 88, 90, 520] Bitstring: 001011000 Swap 3,4: 25 <-> 22 Performed 1 swaps PASS: 8 Current: [23, 12, 11, 22, 25, 34, 64, 88, 90, 520] Bitstring: 010110101 Swap 0,1: 23 <-> 12 Performed 1 swaps PASS: 9 Current: [12, 23, 11, 22, 25, 34, 64, 88, 90, 520] Bitstring: 110101010 Swap 1,2: 23 <-> 11 Performed 1 swaps PASS: 10 Current: [12, 11, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 010101010 Performed 0 swaps PASS: 11 Current: [12, 11, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 110011000 Performed 0 swaps PASS: 12 Current: [12, 11, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 100100000 Performed 0 swaps PASS: 13 Current: [12, 11, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 110101011 Swap 0,1: 12 <-> 11 Performed 1 swaps PASS: 14 Current: [11, 12, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 010101001 Performed 0 swaps PASS: 15 Current: [11, 12, 23, 22, 25, 34, 64, 88, 90, 520] Bitstring: 001010100 Swap 2,3: 23 <-> 22 Performed 1 swaps Final: [11, 12, 22, 23, 25, 34, 64, 88, 90, 520] Passes: 15 SUCCESS! Data is sorted!
In [1]:
#with optimization
import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit.quantum_info import SparsePauliOp
try:
from qiskit_aer.primitives import EstimatorV2
except ImportError:
from qiskit.primitives import EstimatorV2
from qiskit_aer import AerSimulator
from scipy.optimize import minimize
data = [64, 34, 25, 520, 23, 12, 22, 11, 90, 88]
n = len(data)
current_data = data.copy()
pass_num = 0
max_passes = 20 # Prevent infinite loop
print(f"Original data: {data}")
print(f"Target: {sorted(data)}\n")
def circuit_for_pass(current_data, p=1):
n_qubits = len(current_data) - 1
qc = QuantumCircuit(n_qubits)
# Hadamard on all qubits
for i in range(n_qubits):
qc.h(i)
params_gamma = [Parameter(f'γ_{layer}') for layer in range(p)]
params_beta = [Parameter(f'β_{layer}') for layer in range(p)]
for layer in range(p):
# Cost layer - for each neighbor comparison
for i in range(n_qubits - 1):
qc.cx(i, i + 1)
qc.rz(2 * params_gamma[layer], i + 1)
qc.cx(i, i + 1)
# Mixer layer
for i in range(n_qubits):
qc.rx(2 * params_beta[layer], i)
return qc, params_gamma, params_beta
def create_cost_hamiltonian(current_data):
"""Create Hamiltonian for comparisons in current data"""
n_qubits = len(current_data) - 1
pauli_list = []
for i in range(n_qubits):
pauli_str = ["I"] * n_qubits
pauli_str[i] = "Z"
pauli_str = "".join(pauli_str)
# If element is greater than next, we want qubit = 1
if current_data[i] > current_data[i + 1]:
pauli_list.append((pauli_str, 1.0))
else:
pauli_list.append((pauli_str, -1.0))
return SparsePauliOp.from_list(pauli_list)
def optimize_circuit(current_data):
n_qubits = len(current_data) - 1
ansatz, params_gamma, params_beta = circuit_for_pass(current_data, p=1)
all_params = params_gamma + params_beta
cost_hamiltonian = create_cost_hamiltonian(current_data)
estimator = EstimatorV2()
def evaluate_energy(parameters):
try:
job = estimator.run(ansatz,
cost_hamiltonian,
parameter_values=parameters)
result = job.result()
return float(np.real(result.values[0]))
except:
return 1e10
x0 = np.random.random(len(all_params)) * np.pi
result = minimize(evaluate_energy,
x0,
method='L-BFGS-B',
options={'maxiter': 200})
# Measurement
final_circuit = ansatz.copy()
param_dict = {param: val for param, val in zip(all_params, result.x)}
final_circuit = final_circuit.assign_parameters(param_dict)
final_circuit.measure_all()
simulator = AerSimulator()
job = simulator.run(final_circuit, shots=1)
counts = job.result().get_counts()
# Most frequent bitstring
#best_bitstring = max(counts.items(), key=lambda x: x[1])[0]
best_bitstring = list(counts.keys())[0]
return best_bitstring
def is_sorted(data):
"""Check if data is sorted - iterate left to right"""
for i in range(len(data) - 1):
if data[i] > data[i + 1]:
# Found two neighboring elements in wrong order
return False
# All neighboring pairs are in order
return True
while not is_sorted(current_data) and pass_num < max_passes:
pass_num += 1
print(f"\nPASS: {pass_num}")
print(f"Current: {current_data}")
bitstring = optimize_circuit(current_data)
print(f"Bitstring: {bitstring}")
# Check if all zeros - regenerate
if bitstring == "0" * len(bitstring):
print("All zeros - regenerating...")
continue
# Perform swaps based on bitstring
swaps = 0
for i in range(len(current_data) - 1):
bit = int(bitstring[::-1][i])
if bit == 1 and current_data[i] > current_data[i + 1]:
# Correct comparison - should swap
current_data[i], current_data[i +
1] = current_data[i +
1], current_data[i]
swaps += 1
print(
f" Swap {i},{i+1}: {current_data[i+1]} <-> {current_data[i]}")
elif bit == 0 and current_data[i] <= current_data[i + 1]:
# Correct comparison - don't swap
pass
else:
# Incorrect comparison
pass
print(f"Performed {swaps} swaps")
# If no swaps, invert bitstring and try again
if swaps == 0:
print("No swaps performed - inverting bitstring...")
inverted_bitstring = "".join(
"0" if b == "1" else "1" for b in bitstring)
print(f"Inverted bitstring: {inverted_bitstring}")
# Try inverted bitstring
for i in range(len(current_data) - 1):
bit = int(inverted_bitstring[::-1][i])
if bit == 1 and current_data[i] > current_data[i + 1]:
current_data[i], current_data[i + 1] = current_data[
i + 1], current_data[i]
swaps += 1
print(
f" Swap {i},{i+1}: {current_data[i+1]} <-> {current_data[i]}"
)
print(f"Performed {swaps} swaps with inverted bitstring")
print("\n\n")
print(f" Final: {current_data}")
print(f" Passes: {pass_num}")
if is_sorted(current_data):
print(f"\nSUCCESS! Data is sorted!")
else:
print(f"\nFailed to sort in {max_passes} passes")
Original data: [64, 34, 25, 520, 23, 12, 22, 11, 90, 88] Target: [11, 12, 22, 23, 25, 34, 64, 88, 90, 520] PASS: 1 Current: [64, 34, 25, 520, 23, 12, 22, 11, 90, 88] Bitstring: 101011101 Swap 0,1: 64 <-> 34 Swap 3,4: 520 <-> 23 Swap 4,5: 520 <-> 12 Swap 6,7: 22 <-> 11 Swap 8,9: 90 <-> 88 Performed 5 swaps PASS: 2 Current: [34, 64, 25, 23, 12, 520, 11, 22, 88, 90] Bitstring: 010000010 Swap 1,2: 64 <-> 25 Performed 1 swaps PASS: 3 Current: [34, 25, 64, 23, 12, 520, 11, 22, 88, 90] Bitstring: 011101011 Swap 0,1: 34 <-> 25 Swap 3,4: 23 <-> 12 Swap 5,6: 520 <-> 11 Swap 6,7: 520 <-> 22 Swap 7,8: 520 <-> 88 Performed 5 swaps PASS: 4 Current: [25, 34, 64, 12, 23, 11, 22, 88, 520, 90] Bitstring: 100010001 Swap 4,5: 23 <-> 11 Swap 8,9: 520 <-> 90 Performed 2 swaps PASS: 5 Current: [25, 34, 64, 12, 11, 23, 22, 88, 90, 520] Bitstring: 100101111 Swap 2,3: 64 <-> 12 Swap 3,4: 64 <-> 11 Swap 5,6: 23 <-> 22 Performed 3 swaps PASS: 6 Current: [25, 34, 12, 11, 64, 22, 23, 88, 90, 520] Bitstring: 001101110 Swap 1,2: 34 <-> 12 Swap 2,3: 34 <-> 11 Performed 2 swaps PASS: 7 Current: [25, 12, 11, 34, 64, 22, 23, 88, 90, 520] Bitstring: 101001001 Swap 0,1: 25 <-> 12 Performed 1 swaps PASS: 8 Current: [12, 25, 11, 34, 64, 22, 23, 88, 90, 520] Bitstring: 111011001 Swap 4,5: 64 <-> 22 Performed 1 swaps PASS: 9 Current: [12, 25, 11, 34, 22, 64, 23, 88, 90, 520] Bitstring: 001010000 Performed 0 swaps No swaps performed - inverting bitstring... Inverted bitstring: 110101111 Swap 1,2: 25 <-> 11 Swap 3,4: 34 <-> 22 Swap 5,6: 64 <-> 23 Performed 3 swaps with inverted bitstring PASS: 10 Current: [12, 11, 25, 22, 34, 23, 64, 88, 90, 520] Bitstring: 110100011 Swap 0,1: 12 <-> 11 Performed 1 swaps PASS: 11 Current: [11, 12, 25, 22, 34, 23, 64, 88, 90, 520] Bitstring: 110101000 Performed 0 swaps No swaps performed - inverting bitstring... Inverted bitstring: 001010111 Swap 2,3: 25 <-> 22 Swap 4,5: 34 <-> 23 Performed 2 swaps with inverted bitstring PASS: 12 Current: [11, 12, 22, 25, 23, 34, 64, 88, 90, 520] Bitstring: 011010100 Performed 0 swaps No swaps performed - inverting bitstring... Inverted bitstring: 100101011 Swap 3,4: 25 <-> 23 Performed 1 swaps with inverted bitstring Final: [11, 12, 22, 23, 25, 34, 64, 88, 90, 520] Passes: 12 SUCCESS! Data is sorted!
In [3]:
k=0
input_list = [64, 34, 25, 520, 23, 12, 22, 11, 90, 88]
for i in range(len(input_list) - 1): # Počet passů
for j in range(len(input_list) - 1 - i): # Porovnání v každém passu
k = k+1
print(k)
if int(input_list[j]) > int(input_list[j+1]):
input_list[j], input_list[j+1] = input_list[j+1], input_list[j]
print(input_list)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 [11, 12, 22, 23, 25, 34, 64, 88, 90, 520]
In [ ]: