5 edited body; edited title
source | link

Grover's Algorithmalgorithm returns skewed probability distribution

Furthermore, these results do not obtain when I actually run the circuit. Instead of a step-function for the probabilities, when I run 1024 shots I tend to get between 30 and 50 for the unsuccessful results and the successful results are spread between 200 and 460. While it's obvious that the successful results have been selected, the spread is concerning because the math seems to indicate that they should be fairly close together. Moreover, the successful results always fall in the same order, which is also counter intuitive-intuitive given that results are probabilistic. This implies one of two things to me:

Grover's Algorithm returns skewed probability distribution

Furthermore, these results do not obtain when I actually run the circuit. Instead of a step-function for the probabilities, when I run 1024 shots I tend to get between 30 and 50 for the unsuccessful results and the successful results are spread between 200 and 460. While it's obvious that the successful results have been selected, the spread is concerning because the math seems to indicate that they should be fairly close together. Moreover, the successful results always fall in the same order, which is also counter intuitive given that results are probabilistic. This implies one of two things to me:

Grover's algorithm returns skewed probability distribution

Furthermore, these results do not obtain when I actually run the circuit. Instead of a step-function for the probabilities, when I run 1024 shots I tend to get between 30 and 50 for the unsuccessful results and the successful results are spread between 200 and 460. While it's obvious that the successful results have been selected, the spread is concerning because the math seems to indicate that they should be fairly close together. Moreover, the successful results always fall in the same order, which is also counter-intuitive given that results are probabilistic. This implies one of two things to me:

4 Fixed issue with the code so that the oracle is as I described
source | link
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, Aer, execute

# Initialize circuit
m_qubit = QuantumRegister(1)
search_register = QuantumRegister(4)
result_register = ClassicalRegister(4)
ancillaries = QuantumRegister(3)
circuit = QuantumCircuit(search_register, result_register, m_qubit, ancillaries)

# Put M qubit into 1-superposition
circuit.x(m_qubit)
circuit.h(m_qubit)

# Put search qubits into superposition
circuit.h(search_register)

for _ in range(2):

    # Encode S1 * !S2 * S3
    circuit.x( search_register[2] )
    circuit.ccx( search_register[1], search_register[2], ancillaries[0] )
    circuit.ccx( search_register[3], ancillaries[0], ancillaries[1] )
    circuit.x( search_register[2] )

    # Encode S0 +* S1
    circuit.xccx( search_register[0], search_register[1], ancillaries[2] ) 

    circuit.x(# search_register[1]Encode )
oracle ((S0 * S1) circuit.ccx+ (S1 search_register[0],* search_register[1],!S2 ancillaries[2]* S3))
    circuit.x( search_register[0] ancillaries)
    circuit.xccx( search_register[1]ancillaries[1], ancillaries[2], m_qubit[0] )
    circuit.x( ancillaries[2] ancillaries)

    # Encode oracle
    circuit.ccxx( ancillaries[1], ancillaries[2], m_qubit[0] m_qubit)

    # Reset ancillaries to be used later
    circuit.reset(ancillaries)

    # Do rotation about the average
    circuit.h(search_register)
    circuit.x(search_register)
    circuit.ccx( search_register[0], search_register[1], ancillaries[0] )
    circuit.ccx( search_register[2], ancillaries[0], ancillaries[1] )
    circuit.ccx( search_register[3], ancillaries[1], m_qubit[0] )
    circuit.x(search_register)
    circuit.x(m_qubit)
    circuit.h(search_register)

    # Reset ancillaries for use later
    circuit.reset(ancillaries)

circuit.measure(search_register, result_register)

# Run the circuit with a given number of shots
backend_sim = Aer.get_backend('qasm_simulator')
job_sim = execute(circuit, backend_sim, shots = 1024)
result_sim = job_sim.result()

# get_counts returns a dictionary with the bit-strings as keys
# and the number of times the string resulted as the value
print(result_sim.get_counts(circuit))
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, Aer, execute

# Initialize circuit
m_qubit = QuantumRegister(1)
search_register = QuantumRegister(4)
result_register = ClassicalRegister(4)
ancillaries = QuantumRegister(3)
circuit = QuantumCircuit(search_register, result_register, m_qubit, ancillaries)

# Put M qubit into 1-superposition
circuit.x(m_qubit)
circuit.h(m_qubit)

# Put search qubits into superposition
circuit.h(search_register)

for _ in range(2):

    # Encode S1 * !S2 * S3
    circuit.x( search_register[2] )
    circuit.ccx( search_register[1], search_register[2], ancillaries[0] )
    circuit.ccx( search_register[3], ancillaries[0], ancillaries[1] )
    circuit.x( search_register[2] )

    # Encode S0 + S1
    circuit.x( search_register[0] )
    circuit.x( search_register[1] )
    circuit.ccx( search_register[0], search_register[1], ancillaries[2] )
    circuit.x( search_register[0] )
    circuit.x( search_register[1] )
    circuit.x( ancillaries[2] )

    # Encode oracle
    circuit.ccx( ancillaries[1], ancillaries[2], m_qubit[0] )

    # Reset ancillaries to be used later
    circuit.reset(ancillaries)

    # Do rotation about the average
    circuit.h(search_register)
    circuit.x(search_register)
    circuit.ccx( search_register[0], search_register[1], ancillaries[0] )
    circuit.ccx( search_register[2], ancillaries[0], ancillaries[1] )
    circuit.ccx( search_register[3], ancillaries[1], m_qubit[0] )
    circuit.x(search_register)
    circuit.x(m_qubit)
    circuit.h(search_register)

    # Reset ancillaries for use later
    circuit.reset(ancillaries)

circuit.measure(search_register, result_register)

# Run the circuit with a given number of shots
backend_sim = Aer.get_backend('qasm_simulator')
job_sim = execute(circuit, backend_sim, shots = 1024)
result_sim = job_sim.result()

# get_counts returns a dictionary with the bit-strings as keys
# and the number of times the string resulted as the value
print(result_sim.get_counts(circuit))
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, Aer, execute

# Initialize circuit
m_qubit = QuantumRegister(1)
search_register = QuantumRegister(4)
result_register = ClassicalRegister(4)
ancillaries = QuantumRegister(3)
circuit = QuantumCircuit(search_register, result_register, m_qubit, ancillaries)

# Put M qubit into 1-superposition
circuit.x(m_qubit)
circuit.h(m_qubit)

# Put search qubits into superposition
circuit.h(search_register)

for _ in range(2):

    # Encode S1 * !S2 * S3
    circuit.x( search_register[2] )
    circuit.ccx( search_register[1], search_register[2], ancillaries[0] )
    circuit.ccx( search_register[3], ancillaries[0], ancillaries[1] )
    circuit.x( search_register[2] )

    # Encode S0 * S1
    circuit.ccx( search_register[0], search_register[1], ancillaries[2] ) 

    # Encode oracle ((S0 * S1) + (S1 * !S2 * S3))
    circuit.x(ancillaries)
    circuit.ccx( ancillaries[1], ancillaries[2], m_qubit[0] )
    circuit.x(ancillaries)
    circuit.x(m_qubit)

    # Reset ancillaries to be used later
    circuit.reset(ancillaries)

    # Do rotation about the average
    circuit.h(search_register)
    circuit.x(search_register)
    circuit.ccx( search_register[0], search_register[1], ancillaries[0] )
    circuit.ccx( search_register[2], ancillaries[0], ancillaries[1] )
    circuit.ccx( search_register[3], ancillaries[1], m_qubit[0] )
    circuit.x(search_register)
    circuit.x(m_qubit)
    circuit.h(search_register)

    # Reset ancillaries for use later
    circuit.reset(ancillaries)

circuit.measure(search_register, result_register)

# Run the circuit with a given number of shots
backend_sim = Aer.get_backend('qasm_simulator')
job_sim = execute(circuit, backend_sim, shots = 1024)
result_sim = job_sim.result()

# get_counts returns a dictionary with the bit-strings as keys
# and the number of times the string resulted as the value
print(result_sim.get_counts(circuit))
3 edited tags
source | link

$ \frac{1}{1024 \sqrt{2}} \left( -304 \left( \sum_{x \in \{00, 01, 11\}} \left| x \right> \left( \left|00\right> + \left|01\right> + \left|10\right> \right) + \left|1000\right> + \left|1001\right> \right) + 80 \left( \sum_{x = 00}^{11} \left|x\right> \left|11\right> + \left|1010\right> \right) \right) \left( \left|0\right> - \left|1\right> \right)$$$\frac{1}{1024 \sqrt{2}} \left( -304 \left( \sum_{x \in \{00, 01, 11\}} \left| x \right> \left( \left|00\right> + \left|01\right> + \left|10\right> \right) + \left|1000\right> + \left|1001\right> \right) + 80 \left( \sum_{x = 00}^{11} \left|x\right> \left|11\right> + \left|1010\right> \right) \right) \left( \left|0\right> - \left|1\right> \right)$$

$ \frac{1}{1024 \sqrt{2}} \left( -304 \left( \sum_{x \in \{00, 01, 11\}} \left| x \right> \left( \left|00\right> + \left|01\right> + \left|10\right> \right) + \left|1000\right> + \left|1001\right> \right) + 80 \left( \sum_{x = 00}^{11} \left|x\right> \left|11\right> + \left|1010\right> \right) \right) \left( \left|0\right> - \left|1\right> \right)$

$$\frac{1}{1024 \sqrt{2}} \left( -304 \left( \sum_{x \in \{00, 01, 11\}} \left| x \right> \left( \left|00\right> + \left|01\right> + \left|10\right> \right) + \left|1000\right> + \left|1001\right> \right) + 80 \left( \sum_{x = 00}^{11} \left|x\right> \left|11\right> + \left|1010\right> \right) \right) \left( \left|0\right> - \left|1\right> \right)$$

2 Added execution code
source | link
1
source | link