Fix failing: `pytest quantum/q_fourier_transform.py`

[ValentinKlinger]

Repository commit

46379861257d43bb7140d261094bf17dc414950f

Python version (python --version)

Python 3.11.3

Dependencies version (pip freeze)

absl-py==1.4.0 astunparse==1.6.3 beautifulsoup4==4.12.2 black==23.3.0 cachetools==5.3.1 certifi==2023.5.7 cffi==1.15.1 cfgv==3.3.1 charset-normalizer==3.1.0 click==8.1.3 contourpy==1.0.7 cryptography==41.0.0 cycler==0.11.0 dill==0.3.6 distlib==0.3.6 fake-useragent==1.1.3 filelock==3.12.0 flatbuffers==23.5.26 fonttools==4.39.4 gast==0.4.0 google-auth==2.19.0 google-auth-oauthlib==1.0.0 google-pasta==0.2.0 grpcio==1.54.2 h5py==3.8.0 identify==2.5.24 idna==3.4 iniconfig==2.0.0 jax==0.4.10 joblib==1.2.0 keras==2.12.0 kiwisolver==1.4.4 libclang==16.0.0 lxml==4.9.2 Markdown==3.4.3 markdown-it-py==2.2.0 MarkupSafe==2.1.2 matplotlib==3.7.1 mdurl==0.1.2 ml-dtypes==0.1.0 mpmath==1.3.0 mypy==1.3.0 mypy-extensions==1.0.0 networkx==3.1 nodeenv==1.8.0 ntlm-auth==1.5.0 numpy==1.23.5 oauthlib==3.2.2 opencv-python==4.7.0.72 opt-einsum==3.3.0 packaging==23.1 pandas==2.0.2 pathspec==0.11.1 patsy==0.5.3 pbr==5.11.1 Pillow==9.5.0 pip==23.1.2 platformdirs==3.5.1 pluggy==1.0.0 ply==3.11 pre-commit==3.3.2 projectq==0.8.0 protobuf==4.23.2 psutil==5.9.5 pyasn1==0.5.0 pyasn1-modules==0.3.0 pycparser==2.21 Pygments==2.15.1 pyparsing==3.0.9 pytest==7.3.1 python-dateutil==2.8.2 pytz==2023.3 PyYAML==6.0 qiskit==0.43.0 qiskit-aer==0.12.0 qiskit-ibmq-provider==0.20.2 qiskit-terra==0.24.0 requests==2.31.0 requests-ntlm==1.1.0 requests-oauthlib==1.3.1 rich==13.3.5 rsa==4.9 ruff==0.0.270 rustworkx==0.12.1 scikit-fuzzy==0.4.2 scikit-learn==1.2.2 scipy==1.10.1 setuptools==62.6.0 six==1.16.0 soupsieve==2.4.1 statsmodels==0.14.0 stevedore==5.1.0 symengine==0.9.2 sympy==1.12 tensorboard==2.12.3 tensorboard-data-server==0.7.0 tensorflow==2.12.0 tensorflow-estimator==2.12.0 tensorflow-io-gcs-filesystem==0.32.0 termcolor==2.3.0 texttable==1.6.7 threadpoolctl==3.1.0 tweepy==4.14.0 typing_extensions==4.6.2 tzdata==2023.3 urllib3==1.26.16 virtualenv==20.23.0 websocket-client==1.5.2 websockets==11.0.3 Werkzeug==2.3.4 wheel==0.37.1 wrapt==1.14.1 xgboost==1.7.5 yulewalker==0.1.1

Expected behavior

All the tests pass since I haven't made any modifications.

Actual behavior

4 test failed :

FAILED quantum/bb84.py::quantum.bb84.bb84 FAILED quantum/q_fourier_transform.py::quantum.q_fourier_transform.quantum_fourier_transform FAILED quantum/quantum_random.py::quantum.quantum_random.get_random_number FAILED web_programming/instagram_crawler.py::web_programming.instagram_crawler.test_instagram_user

[tianyizheng02]

@ValentinKlinger In our GitHub build workflow, we currently have this:

- name: Run tests
      # See: #6591 for re-enabling tests on Python v3.11
      run: pytest
          --ignore=computer_vision/cnn_classification.py
          --ignore=machine_learning/lstm/lstm_prediction.py
          --ignore=quantum/
          --ignore=project_euler/
          --ignore=scripts/validate_solutions.py
          --cov-report=term-missing:skip-covered
          --cov=. .

So we're aware that some files in quantum/ have failing tests. Apparently they're ignored for now because for a while qiskit was incompatible with Python 3.11 (#6591).

As for web_programming/instagram_crawler.py, I ran it on my own machine and figured out that the code is failing here:

try:
    return extract_user_profile(scripts[4])
except (json.decoder.JSONDecodeError, KeyError):
    return extract_user_profile(scripts[3])

extract_user_profile(scripts[4]) throws a JSONDecodeError, which is caught by the except, but the problem is that extract_user_profile(scripts[3]) throws a JSONDecodeError as well. Since the script never catches this second error, the test fails.

The big problem with having these sorts of web scripts in this repo is that they're difficult to test and easily break if the website they access changes. However, I'm not sure why these tests are passing in pytest in our GitHub build.

[ValentinKlinger]

Okey, thank you, I can't try now because I had to reboot my computer for exams, I'll try when my exam's over.

[cclauss]

Thanks for spotting this @ValentinKlinger

8837 fixed two of the four failing tests.

I changed the title of this issue to reflect the work that remains: Fix pytest quantum/bb84.py quantum/q_fourier_transform.py and remove the corresponding lines: https://github.com/TheAlgorithms/Python/blob/3bfa89dacf877b1d7a62b14f82d54e8de99a838e/.github/workflows/build.yml#L27-L28

[cclauss]

@abhishekchak52, @KevinJoven11 would you be willing to look at these two failing tests?

[rohan472000]

@cclauss , for quantum/bb84.py I observed that the key is generating correct whereas the key (as outputs) provided in doctests are different.

doctest:

     >>> bb84(16, seed=0)
    '1101101100010000'

    >>> bb84(8, seed=0)
    '01011011'

generated output:-

      if __name__ == "__main__":
          print(f"The generated key is : {bb84(8, seed=0)}")
          print(f"The generated key is : {bb84(16, seed=0)}")

The generated key is : 10110001 The generated key is : 0111110111010010

failed doctest:- Expected: '1101101100010000' Got: '0111110111010010'

Expected: '01011011' Got: '10110001'

[cclauss]

These tests used to pass as they are. I assume that changes made in our dependencies changed the generated key values. Please submit a pull request if you see how to fix the tests.

[tianyizheng02]

for quantum/bb84.py I observed that the key is generating is correct whereas the key (as outputs) provided in doctests are different.

@rohan472000 How did you confirm that the keys generated in main are correct? The algorithm relies heavily on random numbers, so I'm not sure how we'd confirm that the algorithm is implemented correctly without an external source.

[tianyizheng02]

These tests used to pass as they are. I assume that changes made in our dependencies changed the generated key values. Please submit a pull request if you see how to fix the tests.

@cclauss The problem is that I believe the contributor originally based the implementation on this Qiskit learning article, but that link is now broken. There's this newer link, but the implementation in this article is significantly different from the contributor's implementation in a few ways. I tried to check whether the current implementation at least matches

if __name__ == "__main__":
    print(f"The generated key is : {bb84(16, seed=0)}")

but the current implementation outright segfaults. I don't know if there's any way for us to confirm whether the original implementation was ever correct (unless one of us happens to be very familiar with Qiskit and quantum key distribution).

Edit: I found the original Qiskit article on the Wayback Machine (snapshot is from October 2022 and the implementation is from November 2022, so this is the closest version of the article). However, the implementation in this older article appears to be the same as the one in the current article, so I have no idea how the contributor originally came up with their implementation.

[rohan472000]

for quantum/bb84.py I observed that the key is generating is correct whereas the key (as outputs) provided in doctests are different.

@rohan472000 How did you confirm that the keys generated in main are correct? The algorithm relies heavily on random numbers, so I'm not sure how we'd confirm that the algorithm is implemented correctly without an external source.

I'm not confirming it, I was running it locally so I observed that, not sure how it was passing the doctest before.

[cclauss]

Code reviews please on

• 8838

This is a seed-based pseudorandom number generator that generates the same result when given the same seed. The problem was that a newer version of qiskit modified their algorithm so the expected result needs to reflect that change.

[rohan472000]

Code reviews please on

• Fix failing pytest quantum/bb84.py #8838

With this doctest's output that u have provided in PR it will pass definitely as I had tried it also in local, but my question is how the previous outputs were passing correctly and why they r failing now??

[rohan472000]

Code reviews please on

• Fix failing pytest quantum/bb84.py #8838

This is a seed-based pseudorandom number generator that generates the same result when given the same seed. The problem was that a newer version of qiskit modified their algorithm so the expected result needs to reflect that change.

Ohh..got it now.

[abhishekchak52]

However, the implementation in this older article appears to be the same as the one in the current article, so I have no idea how the contributor originally came up with their implementation.

@tianyizheng02 The implementation here is based on a summer research I did before Qiskit textbook had their example up. It is completely equivalent in functionality, just organized differently. Does the segfault problem still exist? Nothing in the example itself allocated memory, so it would be something that changed in the dependencies.

@cclauss Sorry for the late response. I'm spread a little thin at the moment. I gather that the updated doctests fixed the problem?

[tianyizheng02]

The implementation here is based on a summer research I did before Qiskit textbook had their example up. It is completely equivalent in functionality, just organized differently. Does the segfault problem still exist? Nothing in the example itself allocated memory, so it would be something that changed in the dependencies.

The segfault problem still exists. My guess is that it could be due to the large circuit size causing memory issues (Qiskit avoids this in their example by using a list of single-qubit circuits rather than one n-qubit circuit), but I'm not familiar enough with Qiskit to know if this is plausible.

[rohan472000]

@cclauss , in quantum/q_fourier_transform.py also the lib qiskit is used, there also doctest are failing in same way as bb84.py.

    Failed example:
        quantum_fourier_transform(2)
    Expected:
        {'00': 2500, '01': 2500, '10': 2500, '11': 2500}
    Got:
        {'10': 2480, '01': 2424, '11': 2485, '00': 2611}

should I raise a PR by changing its output???

[cclauss]

the current implementation outright segfaults

What hardware are you running this on? Please document the steps to reproduce. For extra credit, a GitHub Action that demonstrates the segfault. ;-)

should I raise a PR by changing its output???

I am no FFT guru but my hunch is that the 2500 * 4 dict is the correct answer. It would be great to get more feedback before we change the expectations to fit the actual.

[rohan472000]

QFT is a probabilistic algorithm, the results will have some variability. I can see that after running each time I'm getting new outputs. Yeah..Let's wait for more feedback.

[tianyizheng02]

the current implementation outright segfaults

What hardware are you running this on? Please document the steps to reproduce.

@cclauss My hardware is a MacBook Pro with an Intel i5 chip. You can reproduce the segfault simply by running the file with an input size of 100:

if __name__ == "__main__":
    print(bb84(100, seed=0))

$ python3 quantum/bb84.py
zsh: segmentation fault  python3 quantum/bb84.py

I was testing it on such a large value because n = 100 is the input size used in the Qiskit article's example.

[tianyizheng02]

For extra credit, a GitHub Action that demonstrates the segfault. ;-)

@cclauss See the failing build for my demo PR #8841 :^)

Fatal Python error: /home/runner/work/_temp/f21d497d-6cae-49bd-acfd-3dc4c87d955b.sh: line 1:  1859 Segmentation fault      (core dumped) pytest --ignore=quantum/q_fourier_transform.py --ignore=project_euler/ --ignore=scripts/validate_solutions.py --cov-report=term-missing:skip-covered --cov=. .
quantum/bb84.py 
Error: Process completed with exit code 139.