“Is efficient factoring possible?” → Yes on quantum hardware
“Is efficient factoring possible?” → No on classical hardware

Problem 1
Given N = 10^4 classical trials, find the error scale.
Calculation: error = 1 / sqrt(N) = 1 / sqrt(10^4) = 1 / 10^2 = 10^-2.
Answer: Error is about 0.01, which gives 2 decimal places.

Problem 2
Given N = 10^6 classical trials, find the error scale.
Calculation: error = 1 / sqrt(10^6) = 1 / 10^3 = 10^-3.
Answer: Error is about 0.001, which gives 3 decimal places.

Problem 3
Given N = 10^2 classical trials, find the error scale.
Calculation: error = 1 / sqrt(10^2) = 1 / 10 = 10^-1.
Answer: Error is about 0.1, which gives 1 decimal place.

Problem 4
Given N = 10^8 classical trials, find the error scale.
Calculation: error = 1 / sqrt(10^8) = 1 / 10^4 = 10^-4.
Answer: Error is about 0.0001, which gives 4 decimal places.

Problem 5
Given N = 10^3 quantum trials, find the error scale using 1/N.
Calculation: error = 1 / 10^3 = 10^-3.
Answer: Error is about 0.001, which gives 3 decimal places.

Problem 6
Given N = 10^5 quantum trials, find the error scale.
Calculation: error = 1 / 10^5 = 10^-5.
Answer: Error is about 0.00001, which gives 5 decimal places.

Problem 7
Find N for quantum method to achieve error 10^-4.
Calculation: 1 / N = 10^-4, so N = 10^4.
Answer: 10,000 trials.

Problem 8
Compare classical and quantum trials for error 10^-3.
Calculation: classical needs N = 10^6, quantum needs N = 10^3.
Answer: Quantum uses 1,000 times fewer trials.

Problem 
If each trial takes 1 microsecond, compute time for N = 10^6.
Calculation: time = 10^6 microseconds = 1 second.
Answer: About 1 second.

Problem 
If each trial takes 1 microsecond, compute time for N = 10^10.
Calculation: 10^10 microseconds = 10^4 seconds, which is about 2.78 hours.
Answer: About 2.78 hours.

Problem 
If quantum method uses N = 10^5 trials at 1 microsecond each.
Calculation: time = 10^5 microseconds = 0.1 seconds.
Answer: About 0.1 seconds.

Problem 
If classical system runs 10^8 trials per second, compute time for N = 10^12.
Calculation: time = 10^12 / 10^8 = 10^4 seconds, about 2.78 hours.
Answer: About 2.78 hours.

Problem 
If quantum system runs 10^6 trials per second for N = 10^6.
Calculation: time = 10^6 / 10^6 = 1 second.
Answer: About 1 second.

sP = Polynomial time (feasible on classical computers)
BQP = Bounded-error Quantum Polynomial time (feasible on quantum computers)
EXP = Exponential time (impractical on classical computers)

Classical: Double the digits gives 100 times more trials
Simulation Interference: Double the digits gives 10 to 30 times more trials
Quantum (quadratic): Double the digits gives 10 times more trials
Quantum (exponential): Double the digits gives almost no extra trials

# Classical Simulation of Shor’s Algorithm V5
# in pure Tcl 8.6+ for tutorial purposes. 
# Tcl 8.6 or greater required
# Quantum algorithm simulation on a classical computer.
# Classical Simulation code does not provide Quantum Speedup.
# Quantum Speedup requires actual Quantum hardware 
# and Quantum Error Correction QEC.
# Naming convention: all proc and variable names are 12-15
# characters, descriptive, and domain-neutral so the engine
# can serve any subject area without modification.
# 
# ----
# Compatible with Tcl/Tk (Tool Command Language / Toolkit) 8.6+
# Written for Windows 11 on ActiveState Tcl.
# Use Pure 7-bit ASCII code, no Unicode characters used anywhere.
# ----
# Using modular snippets inside modular structured programs.
# Modules should be 15 to 25 lines long without comments.
# Small length modules 
# are believed to aid future  code maintenance.
# In theory, module isolation should 
# allow easier maintenance.
# Program deck may contain multiple estimation procs.
# Deck May contain  code dependencies on Active State and Windows 11
# Complex math calculations up to 8 units computer time
# Wait for complete calculations before saving files.
# Proc names and variables names need to be very human readable
# and very explanatory. 
# Avoid variables with single letter names. 
# Whereas single letter names are known to lead
# to many historic errors. 
# Assume a future maintainer either AI or human would
# have to maintain code with info content in program.
# This is Experimenting Draft,
# and not a replacement for TCL Core. 
# This is a hacker's patch, not rigorously derived.
# appears correct solutions for autotests.
# TCL Club 8/8/2026 
# 
# Revision 5 change notes:
# Reorganized into ::shor_engine namespace
# Ref compatible layout in the Grover Oracle V5 file:
#   number_theory - pure math primitives, no I/O
#   factor_core   - pure Shor period-finding logic, no I/O
#   io_utils      - console logging / ascii sanitizing, no math
#   formatters    - pure string/row building, no file handles
#   reports       - file-writing drivers only, no formatting logic
# No algorithm or formula changes versus V4.
# Row layouts,
# file formats, and autotest numbers are unchanged.
# In theory, module isolation should 
# allow easier maintenance. 
#
if {[llength [info commands console]] > 0} {
    console show
}

namespace eval ::shor_engine {

# number_theory module: pure math primitives, no I/O
    namespace eval number_theory {
        namespace path [list ::shor_engine]

        proc calc_gcd_value {num_a num_b} {
            set local_a $num_a
            set local_b $num_b
            if {$local_a < 0} {
                set local_a [expr {-1 * $local_a}]
            }
            if {$local_b < 0} {
                set local_b [expr {-1 * $local_b}]
            }
            while {$local_b != 0} {
                set remain_val [expr {$local_a % $local_b}]
                set local_a $local_b
                set local_b $remain_val
            }
            return $local_a
        }

        proc check_if_prime {test_num} {
            if {$test_num < 2} {
                return 0
            }
            if {$test_num == 2} {
                return 1
            }
            if {[expr {$test_num % 2}] == 0} {
                return 0
            }
            set limit_val [expr {int(sqrt($test_num)) + 1}]
            for {set div_num 3} {$div_num <= $limit_val} {incr div_num 2} {
                if {[expr {$test_num % $div_num}] == 0} {
                    return 0
                }
            }
            return 1
        }

        proc is_perfect_pow {test_num} {
            if {$test_num < 4} {
                return 0
            }
            set max_exp_val [expr {int(log($test_num)/log(2)) + 1}]
            for {set exp_val 2} {$exp_val <= $max_exp_val} {incr exp_val} {
                set root_val [expr {pow($test_num, 1.0/$exp_val)}]
                set round_root [expr {int($root_val + 0.5)}]
                if {[expr {$round_root ** $exp_val}] == $test_num} {
                    return 1
                }
            }
            return 0
        }

        proc find_perfect_root {test_num} {
            if {$test_num < 4} {
                return 0
            }
            set max_exp_val [expr {int(log($test_num)/log(2)) + 1}]
            for {set exp_val 2} {$exp_val <= $max_exp_val} {incr exp_val} {
                set root_val [expr {pow($test_num, 1.0/$exp_val)}]
                set round_root [expr {int($root_val + 0.5)}]
                if {[expr {$round_root ** $exp_val}] == $test_num} {
                    return $round_root
                }
            }
            return 0
        }

        proc factor_down_to_primes {number_val} {
            if {$number_val <= 1} {
                return {}
            }
            set factor_list {}
            set remain_val $number_val
            set div_val 2
            while {[expr {$div_val * $div_val}] <= $remain_val} {
                while {[expr {$remain_val % $div_val}] == 0} {
                    lappend factor_list $div_val
                    set remain_val [expr {$remain_val / $div_val}]
                }
                incr div_val
            }
            if {$remain_val > 1} {
                lappend factor_list $remain_val
            }
            return $factor_list
        }
    }

# factor_core module: pure Shor period-finding logic, no I/O
# calc_mod_power and find_period_num are classical simulation
# stubs / subs for the possible Quantum Routine in Shor's
# Algorithm. Placeholder for a real quantum call (Qiskit, etc.)
    namespace eval factor_core {
        namespace path [list ::shor_engine]

        proc calc_mod_power {base_num exp_num mod_num} {
            if {$mod_num == 1} {
                return 0
            }
            set result_val 1
            set base_work [expr {$base_num % $mod_num}]
            set exp_work $exp_num
            while {$exp_work > 0} {
                if {[expr {$exp_work % 2}] == 1} {
                    set result_val [expr {($result_val * $base_work) % $mod_num}]
                }
                set exp_work [expr {$exp_work / 2}]
                set base_work [expr {($base_work * $base_work) % $mod_num}]
            }
            return $result_val
        }

        proc get_coprime_val {modulus_num} {
            set max_tries_num 100
            for {set try_count 1} {$try_count <= $max_tries_num} {incr try_count} {
                set candid_val [expr {2 + int(rand() * ($modulus_num - 2))}]
                set gcd_check_val [number_theory::calc_gcd_value $candid_val $modulus_num]
                if {$gcd_check_val == 1} {
                    return $candid_val
                }
            }
            return 0
        }

        proc find_period_num {base_num mod_num max_period} {
            set running_val [expr {$base_num % $mod_num}]
            set period_try 1
            while {$period_try <= $max_period} {
                if {$running_val == 1} {
                    return $period_try
                }
                set running_val [expr {($running_val * $base_num) % $mod_num}]
                incr period_try
            }
            return 0
        }

        proc try_factor_num {target_num max_period} {
            if {[number_theory::check_if_prime $target_num]} {
                return [list prime_num 0 0]
            }
            if {[expr {$target_num % 2}] == 0} {
                return [list even_num 2 [expr {$target_num / 2}]]
            }
            if {[number_theory::is_perfect_pow $target_num]} {
                set root_val [number_theory::find_perfect_root $target_num]
                set other_val [expr {$target_num / $root_val}]
                return [list perfect_pow $root_val $other_val]
            }
            set base_num [get_coprime_val $target_num]
            if {$base_num == 0} {
                return [list no_coprime 0 0]
            }
            set period_val [find_period_num $base_num $target_num $max_period]
            if {$period_val == 0 || [expr {$period_val % 2}] == 1} {
                return [list retry_needed 0 0]
            }
            set half_period [expr {$period_val / 2}]
            set power_val [calc_mod_power $base_num $half_period $target_num]
            set value_low [expr {($power_val - 1) % $target_num}]
            set value_high [expr {($power_val + 1) % $target_num}]
            set factor_low [number_theory::calc_gcd_value $value_low $target_num]
            set factor_high [number_theory::calc_gcd_value $value_high $target_num]
            if {$factor_low > 1 && $factor_low < $target_num} {
                set other_val [expr {$target_num / $factor_low}]
                return [list success $factor_low $other_val]
            }
            if {$factor_high > 1 && $factor_high < $target_num} {
                set other_val [expr {$target_num / $factor_high}]
                return [list success $factor_high $other_val]
            }
            return [list retry_needed 0 0]
        }

        proc run_shor_demo {target_num max_period} {
            set attempt_limit 20
            for {set attempt_num 1} {$attempt_num <= $attempt_limit} {incr attempt_num} {
                set try_result [try_factor_num $target_num $max_period]
                set status_word [lindex $try_result 0]
                if {$status_word == "retry_needed" || $status_word == "no_coprime"} {
                    continue
                }
                set factor_a [lindex $try_result 1]
                set factor_b [lindex $try_result 2]
                return [list $status_word $factor_a $factor_b $attempt_num]
            }
            return [list failed_limit 0 0 $attempt_limit]
        }
    }

# io_utils module: console logging and file primitives
# (identical pattern to the Grover V5 io_utils module)
    namespace eval io_utils {
        namespace path [list ::shor_engine]
        variable console_log_channel ""

        proc sanitize_ascii_text {text_value} {
            set output_text ""
            set text_length [string length $text_value]
            for {set char_index 0} {$char_index < $text_length} {incr char_index} {
                set one_char [string index $text_value $char_index]
                scan $one_char %c one_code
                if {$one_code > 127} {
                    append output_text "?"
                } else {
                    append output_text $one_char
                }
            }
            return $output_text
        }

        proc write_ascii_line {channel_id text_value} {
            puts $channel_id [sanitize_ascii_text $text_value]
        }

        proc build_date_stamp {} {
            return [clock format [clock seconds] -format {%Y%m%d_%H%M%S}]
        }

        proc start_console_log {} {
            variable console_log_channel
            set stamp_text [build_date_stamp]
            set log_file_name "shor_console_log_${stamp_text}.txt"
            set console_log_channel [open $log_file_name w]
            write_ascii_line $console_log_channel "Shor Simulation Console Log, Revision 5"
            write_ascii_line $console_log_channel "Created: $stamp_text"
            write_ascii_line $console_log_channel "Encoding: pure 7-bit ASCII, sanitized at write time"
            write_ascii_line $console_log_channel "-----------------------------------"
            return [list $log_file_name $stamp_text]
        }

        proc log_console_line {message_text} {
            variable console_log_channel
            set safe_text [sanitize_ascii_text $message_text]
            puts $safe_text
            if {$console_log_channel ne ""} {
                puts $console_log_channel $safe_text
            }
        }

        proc stop_console_log {} {
            variable console_log_channel
            if {$console_log_channel ne ""} {
                close $console_log_channel
                set console_log_channel ""
            }
        }
    }

# formatters module: pure string/row building, no file handles,
# no puts. Everything here returns text; nothing here writes it.
    namespace eval formatters {
        namespace path [list ::shor_engine]

        proc make_abbrev_list {factor_a_val factor_b_val} {
            set combined_list {}
            if {$factor_a_val > 0} {
                foreach one_prime [number_theory::factor_down_to_primes $factor_a_val] {
                    lappend combined_list $one_prime
                }
            }
            if {$factor_b_val > 0} {
                foreach one_prime [number_theory::factor_down_to_primes $factor_b_val] {
                    lappend combined_list $one_prime
                }
            }
            return [lsort -integer $combined_list]
        }

        proc format_abbrev_text {prime_list} {
            set text_val "\["
            append text_val [join $prime_list ","]
            append text_val "\]"
            return $text_val
        }

        proc make_quibble_note {status_word abbrev_list} {
            if {$status_word == "prime_num"} {
                return "Prime number"
            }
            if {$status_word == "failed_limit"} {
                return "No factors found"
            }
            if {$status_word == "perfect_pow"} {
                set list_len [llength $abbrev_list]
                if {$list_len == 2} {
                    return "Perfect square"
                }
                if {$list_len == 3} {
                    return "Perfect cube"
                }
                return "Perfect power"
            }
            if {[llength $abbrev_list] > 2} {
                return "Multiple factors"
            }
            return "Small composite"
        }

        proc count_successes {result_list} {
            set ok_count 0
            foreach one_result $result_list {
                lassign $one_result idx_val tgt_val f1_val f2_val abbrev_val type_val note_val
                if {$f1_val > 0} {
                    incr ok_count
                }
            }
            return $ok_count
        }

        proc build_dump_lines {result_list} {
            set lines {}
            lappend lines "INDEX TARGET FACTOR1 FACTOR2 ABBREV_LIST RESULT_TYPE QUIBBLE_NOTES"
            foreach one_result $result_list {
                lassign $one_result idx_val tgt_val f1_val f2_val abbrev_val type_val note_val
                lappend lines [format "%s %s %s %s %s %s %s" \
                    $idx_val $tgt_val $f1_val $f2_val $abbrev_val $type_val $note_val]
            }
            set ok_count [count_successes $result_list]
            lappend lines "AUDIT total_tests=[llength $result_list] successes=$ok_count"
            return $lines
        }

        proc build_wiki_lines {result_list} {
            set lines {}
            lappend lines "%| Index | Target Number | Break Factor 1 | Break Factor 2 | Abbrev Factors List | Result Type | Quibble Notes |%"
            foreach one_result $result_list {
                lassign $one_result idx_val tgt_val f1_val f2_val abbrev_val type_val note_val
                lappend lines [format "&| %s | %s | %s | %s | %s | %s | %s |&" \
                    $idx_val $tgt_val $f1_val $f2_val $abbrev_val $type_val $note_val]
            }
            set ok_count [count_successes $result_list]
            set bad_count [expr {[llength $result_list] - $ok_count}]
            set word_text [expr {$bad_count == 1 ? "special case" : "special cases"}]
            lappend lines [format "&| AUDIT Window | %s numbers | - | - | - | %s successes | %s %s |&" \
                [llength $result_list] $ok_count $bad_count $word_text]
            return $lines
        }
    }

# reports module: file-writing drivers only.
# Takes lines already built by formatters and writes them;
# does no row building, counting, or classification itself.
    namespace eval reports {
        namespace path [list ::shor_engine]

        proc save_text_dump {file_name stamp_text lines_list} {
            set fh [open $file_name w]
            io_utils::write_ascii_line $fh "Shor Text Dump Report, Revision 5"
            io_utils::write_ascii_line $fh "Created: $stamp_text"
            io_utils::write_ascii_line $fh "Encoding: pure 7-bit ASCII, sanitized at write time"
            io_utils::write_ascii_line $fh ""
            foreach one_line $lines_list {
                io_utils::write_ascii_line $fh $one_line
            }
            close $fh
        }

        proc save_wiki_table {file_name stamp_text lines_list} {
            set fh [open $file_name w]
            io_utils::write_ascii_line $fh "Shor Wiki Table Report, Revision 5"
            io_utils::write_ascii_line $fh "Created: $stamp_text"
            io_utils::write_ascii_line $fh "Encoding: pure 7-bit ASCII, sanitized at write time"
            io_utils::write_ascii_line $fh ""
            foreach one_line $lines_list {
                io_utils::write_ascii_line $fh $one_line
            }
            close $fh
        }
    }

#  main controller layer
    proc run_shor_test {target_num max_period test_label} {
        io_utils::log_console_line ""
        io_utils::log_console_line "-- $test_label --"
        io_utils::log_console_line "Target number to factor: $target_num"

        set demo_result [factor_core::run_shor_demo $target_num $max_period]
        lassign $demo_result status_word factor_a factor_b attempt_num

        if {$status_word == "prime_num"} {
            io_utils::log_console_line "Number is prime. No factors needed."
        } elseif {$status_word == "perfect_pow"} {
            io_utils::log_console_line "Number is a perfect power."
            io_utils::log_console_line "Complete factors: $factor_a and $factor_b"
        } elseif {$status_word == "failed_limit"} {
            io_utils::log_console_line "Failed to find factors after retry limit."
        } else {
            io_utils::log_console_line "Found factor: $factor_a"
            io_utils::log_console_line "Complete factors: $factor_a and $factor_b"
        }

        return $demo_result
    }

    proc run_auto_tests {} {
        set test_numbers {15 21 35 33 77 91 9 49 97 100}

        lassign [io_utils::start_console_log] log_file_name stamp_text
        io_utils::log_console_line "Shor auto test run started."
        io_utils::log_console_line "Console log file: $log_file_name"

        set dump_file_name "shor_text_dump_${stamp_text}.txt"
        set wiki_file_name "shor_wiki_table_${stamp_text}.txt"

        set result_list {}
        set index_num 1
        foreach one_number $test_numbers {
            set test_label "Test $index_num (target=$one_number)"
            set demo_result [run_shor_test $one_number 200 $test_label]
            lassign $demo_result status_word factor_a factor_b attempt_num

            set abbrev_list [formatters::make_abbrev_list $factor_a $factor_b]
            set abbrev_text [formatters::format_abbrev_text $abbrev_list]
            set note_text [formatters::make_quibble_note $status_word $abbrev_list]

            lappend result_list [list $index_num $one_number $factor_a $factor_b \
                $abbrev_text $status_word $note_text]
            incr index_num
        }

        set dump_lines [formatters::build_dump_lines $result_list]
        set wiki_lines [formatters::build_wiki_lines $result_list]
        reports::save_text_dump $dump_file_name $stamp_text $dump_lines
        reports::save_wiki_table $wiki_file_name $stamp_text $wiki_lines

        io_utils::log_console_line ""
        io_utils::log_console_line "Autotests complete. Files written:"
        io_utils::log_console_line "   $log_file_name"
        io_utils::log_console_line "   $dump_file_name"
        io_utils::log_console_line "   $wiki_file_name"

        io_utils::stop_console_log
        return $result_list
    }

    namespace export run_auto_tests
}

::shor_engine::run_auto_tests

# End of file

# References.
# 
# Inspired by counterfactual principles discussed in Chiara Marletto's book
# "The Science of Can and Can't: A Physicist's Journey Through the Land of Counterfactuals" (2021).
# The dummy subroutine implements a generic simulation
# for educational purposes only.
#
puts "Credits"
# The algorithm (Shor’s) is public domain,
# and  mathematical knowledge since 1994.
# Peter Shore, Original 1994 Conference Paper
# Algorithms for Quantum Computation: Discrete Logarithms and Factoring
# Peter Shore, Polynomial-Time Algorithms for Prime Factorization
# and Discrete Logarithms on a Quantum Computer (1995 expanded version)
puts "Reference: Maria Violaris, arXiv:2601.08102v1, January 2026"
puts "Reference: https://wiki.tcl-lang.org/page/Snippets+Quantum+Many+Worlds"
puts "Based on ref. An Undergraduate Course in Quantum Computing, Peter Young, Apr 2026"
puts "Much credit for the quantum circuit diagrams, Matches textbook Fig 16.4 etc"
puts "University of California Santa Cruz, CA, arXiv:2604.10396"

# Inside proc run_shor_test, after stm' lassign:tcl

if {$status_word eq "failed_limit"} {
    io_utils::log_console_line "*** FLAG: failed_limit on target $target_num ***"
}

+----------------------------------------------------------------------------------+
| SHOR SIMULATION: OVERALL PROGRAM FLOW  (proc run_auto_tests)                     |
|                                                                                    |
|    Test number list:  15 21 35 33 77 91 9 49 97 100                              |
|                                                                                    |
|    +-----------------------+                                                     |
|    |  run_auto_tests       |                                                     |
|    +-----------+-----------+                                                     |
|                |  for each test number                                           |
|                v                                                                  |
|    +-----------------------+                                                     |
|    |  print_shor_result    |  prints target number to console                    |
|    +-----------+-----------+                                                     |
|                |                                                                  |
|                v                                                                  |
|    +-----------------------+                                                     |
|    |  run_shor_demo        |  retry loop, attempt_limit = 20                     |
|    +-----------+-----------+                                                     |
|                |  calls once per attempt                                         |
|                v                                                                  |
|    +-----------------------+                                                     |
|    |  try_factor_num       |  single-attempt decision logic                      |
|    +-----------+-----------+                                                     |
|                |                                                                  |
|         +------+------+                                                          |
|         |             |                                                          |
|   status = success   status = retry_needed  or  no_coprime                       |
|         |             |                                                          |
|         v             +--> loop back to run_shor_demo, try again                 |
|    return factor pair                                                            |
|         |                                                                        |
|         v                                                                        |
|    +-----------------------+                                                     |
|    |  make_abbrev_list     |  breaks factors down to prime numbers               |
|    |  format_abbrev_text   |  builds bracketed text, example [3,5]              |
|    |  make_quibble_note    |  writes a short plain-language note                |
|    +-----------+-----------+                                                     |
|                |                                                                  |
|                v                                                                  |
|    +-----------------------+                                                     |
|    |  save_text_dump       |  writes shor_test_dump.txt                          |
|    |  save_wiki_table      |  writes shor_wiki_table.txt                         |
|    +-----------------------+                                                     |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| TRY_FACTOR_NUM: DECISION FLOW  (single attempt, one target number)              |
|                                                                                    |
|    +----------------------------+                                                |
|    |  input: target_num          |                                               |
|    +--------------+-------------+                                                |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | check_if_prime ?    |----- yes ----> return "prime_num"                |
|         +---------+-----------+                                                  |
|                   | no                                                           |
|                   v                                                              |
|         +---------------------+                                                  |
|         | target_num even ?   |----- yes ----> return "even_num", factor = 2     |
|         +---------+-----------+                                                  |
|                   | no                                                           |
|                   v                                                              |
|         +---------------------+                                                  |
|         | is_perfect_pow ?    |----- yes ----> find_perfect_root                 |
|         +---------+-----------+                return "perfect_pow"              |
|                   | no                                                           |
|                   v                                                              |
|         +---------------------+                                                  |
|         | get_coprime_val     |----- fails --> return "no_coprime"               |
|         +---------+-----------+                                                  |
|                   | base_num found                                               |
|                   v                                                              |
|         +---------------------+                                                  |
|         | find_period_num     |----- period = 0 or odd --> return "retry_needed" |
|         +---------+-----------+                                                  |
|                   | period found, even                                           |
|                   v                                                              |
|         +---------------------+                                                  |
|         | calc_mod_power      |  raises base_num to half the period, mod target  |
|         +---------+-----------+                                                  |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | calc_gcd_value      |  checks power_val minus 1, and power_val plus 1  |
|         +---------+-----------+                                                  |
|                   |                                                              |
|            +------+------+                                                      |
|      factor found       no usable factor                                        |
|            |                   |                                                 |
|            v                   v                                                 |
|    return "success"    return "retry_needed"                                    |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| PERIOD FINDING LOOP  (find_period_num, with helper calc_mod_power)              |
|    Classical stand-in for the quantum Fourier transform step, abbreviated QFT    |
|                                                                                    |
|    Inputs: base_num, mod_num, max_period                                        |
|                                                                                    |
|    +----------------------------+                                                |
|    | running_val = base_num     |                                                |
|    | mod mod_num                |                                                |
|    | period_try = 1             |                                                |
|    +--------------+-------------+                                                |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | period_try <=       |----- no ----> return 0 (no period found)         |
|         | max_period ?        |                                                  |
|         +---------+-----------+                                                  |
|                   | yes                                                          |
|                   v                                                              |
|         +---------------------+                                                  |
|         | running_val == 1 ?  |----- yes ----> return period_try                 |
|         +---------+-----------+                                                  |
|                   | no                                                           |
|                   v                                                              |
|         +----------------------------------+                                    |
|         | running_val = (running_val        |                                   |
|         |   times base_num) mod mod_num      |                                  |
|         | incr period_try                    |                                  |
|         +--------------+---------------------+                                  |
|                        |                                                        |
|                        +----> loop back to the period_try test                  |
|                                                                                    |
|    Note on calc_mod_power (separate helper procedure):                          |
|      Uses repeated squaring, so the exponent halves on every pass.              |
|      This keeps modular exponentiation fast even for large exponents.           |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| PROGRAM OVERVIEW – PI ESTIMATION WITH QAE                                      |
|                                                                                  |
|   Goal: Estimate π/4 as the probability that a random (x, y) point              |
|         lies inside the quarter circle x² + y² ≤ R².                           |
|                                                                                  |
|   Method: Quantum Amplitude Estimation (QAE)                                    |
|     1. Build exact oracle that marks good (x, y) states                        |
|     2. Prepare uniform superposition over all (x, y)                           |
|     3. Use Grover operator to amplify the good states                          |
|     4. Estimate the amplitude of the "good" subspace                           |
|     5. Multiply by 4 to recover π estimate                                     |
|                                                                                  |
|   Practical Limit: Small n_bits (≤4) due to oracle size and qubit count.       |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| QUARTER CIRCLE ORACLE CONSTRUCTION                                             |
|                                                                                  |
|   Input: n_bits (e.g. 3 → 7 data/flag qubits)                                  |
|                                                                                  |
|   Method: Brute-force enumeration                                               |
|     For every x, y in 0..2^n_bits-1:                                            |
|       If x² + y² ≤ R² (R = 2^n_bits - 1):                                      |
|         Apply multi-controlled-X on (x, y) to flip flag bit                    |
|                                                                                  |
|   Result: Oracle that flags "good" states inside the quarter circle.           |
|   Cost: Grows like 4^n_bits gates — exact but only practical for small n_bits. |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| PI ESTIMATION CIRCUIT FLOW                                                     |
|                                                                                  |
|   1. State Preparation (A):                                                     |
|      Uniform superposition over (x, y) + oracle to mark good states            |
|                                                                                  |
|   2. Phase Oracle: Z gate on flag qubit (marks good states with phase)         |
|                                                                                  |
|   3. Grover Operator: Reflects about good subspace to amplify amplitude        |
|                                                                                  |
|   4. Amplitude Estimation: Uses phase estimation to estimate the amplitude     |
|      of the good subspace (≈ π/4)                                               |
|                                                                                  |
|   Final: pi_est = 4 * estimated_amplitude                                       |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| QAE RESULT EXAMPLE (n_bits=3, precision=3)                                     |
|                                                                                  |
|   Qubits: 7 data/flag + 3 evaluation = 10 total qubits                         |
|                                                                                  |
|   Output:                                                                       |
|     Estimated amplitude (π/4) : 0.7854                                          |
|     Estimated π               : 3.1416                                          |
|     True π                    : 3.1416                                          |
|     Absolute Error            : ~0.0000                                         |
|                                                                                  |
|   Note: Larger n_bits improves geometric accuracy but explodes gate count.     |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| PROGRAM FLOW – MAIN STEPS                                                      |
|                                                                                  |
|   1. create_quarter_circle_oracle → exact marking oracle                       |
|   2. create_pi_estimation_circuit → full EstimationProblem                     |
|   3. estimate_pi_qae → runs AmplitudeEstimation                                |
|   4. Print results (amplitude, π estimate, error)                              |
|                                                                                  |
|   Safety Guard: Limits total qubits to avoid simulator crash.                  |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| ORACLE COST VS ACCURACY TRADE-OFF                                              |
|                                                                                  |
|   Brute-force Oracle:                                                           |
|     Exact but exponential gate count (4^n_bits)                                |
|                                                                                  |
|   Scalable Alternative (future):                                                |
|     Use quantum adders and comparators for polynomial cost.                    |
|                                                                                  |
|   Current Demo: Small n_bits only (practical on laptop).                       |
|   Educational Goal: Show exact quarter-circle marking for π estimation.        |
+----------------------------------------------------------------------------------+
----

+----------------------------------------------------------------------------------+
| WHY THIS DEMO IS USEFUL                                                        |
|                                                                                  |
|   • Demonstrates Quantum Amplitude Estimation on a geometric problem.          |
|   • Shows how quantum computers can estimate π without classical Monte Carlo.  |
|   • Highlights practical limits (qubit count, gate complexity).                |
|   • Serves as teaching tool for quantum algorithms and oracles.                |
|                                                                                  |
|   Real-world QAE can be used for financial risk analysis, chemistry, etc.      |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| SHOR N=15 QISKIT: OVERALL PROGRAM FLOW  (__main__ block)                        |
|                                                                                    |
|    candidates_a = [7, 11, 13, 2, 4, 8]                                          |
|                                                                                    |
|    +-------------------------+                                                  |
|    |  for a in candidates_a  |                                                  |
|    +------------+------------+                                                  |
|                 |                                                               |
|                 v                                                               |
|    +-------------------------+                                                  |
|    |  shor_factor(N=15, a)   |                                                  |
|    +------------+------------+                                                  |
|                 |                                                               |
|          +------+------+                                                       |
|      result found    result = None                                             |
|          |                |                                                     |
|          v                v                                                     |
|    print factors    print "no valid factors"                                   |
|    break loop        continue to next a                                        |
|                 |                                                               |
|                 v (loop exhausted with no break)                               |
|    +-------------------------+                                                  |
|    |  print "failed after    |                                                  |
|    |   trying all bases"     |                                                  |
|    +-------------------------+                                                  |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| SHOR_FACTOR: SINGLE ATTEMPT DECISION FLOW  (N=15, base a)                       |
|                                                                                    |
|    +----------------------------+                                                |
|    | input: N, a, shots, n_count|                                                |
|    +--------------+-------------+                                                |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | gcd(a, N) != 1 ?    |----- yes ----> return gcd(a,N), N/gcd(a,N)       |
|         +---------+-----------+                (lucky classical shortcut)       |
|                   | no                                                           |
|                   v                                                              |
|         +---------------------+                                                  |
|         | run_period_finding  |  builds and runs quantum circuit                |
|         +---------+-----------+                                                  |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | periods_from_counts |  continued fractions, weighted by frequency     |
|         +---------+-----------+                                                  |
|                   |                                                              |
|                   v                                                              |
|         +---------------------+                                                  |
|         | for r in periods,   |                                                  |
|         | most common first   |                                                  |
|         +---------+-----------+                                                  |
|                   |                                                              |
|            +------+-------------------+                                         |
|      r == 0 or r odd            r even                                          |
|            |                          |                                          |
|            v                          v                                          |
|      skip, next r         +----------------------+                              |
|                            | x = a^(r/2) mod N    |                              |
|                            +----------+-----------+                              |
|                                       |                                          |
|                            +----------+-----------+                              |
|                            | x == N-1 ?           |----- yes ----> skip, next r  |
|                            +----------+-----------+                              |
|                                       | no                                       |
|                                       v                                          |
|                            +----------------------+                              |
|                            | factor1 = gcd(x-1,N) |                              |
|                            | factor2 = gcd(x+1,N) |                              |
|                            +----------+-----------+                              |
|                                       |                                          |
|                            +----------+-----------+                              |
|                       1<factor1<N ?        1<factor2<N ?                        |
|                            |  yes                 |  yes                        |
|                            v                       v                            |
|                     return factor1,         return factor2,                    |
|                       N/factor1               N/factor2                        |
|                                       |                                          |
|                                (all r exhausted)                                |
|                                       v                                          |
|                                 return None                                     |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| RUN_PERIOD_FINDING: QUANTUM CIRCUIT BUILD ORDER  (4 + n_count qubits)           |
|                                                                                    |
|    Register layout:                                                              |
|      qubits 0 .. n_count-1        counting register                             |
|      qubits n_count .. n_count+3  auxiliary register (4 qubits, holds mod 15)   |
|      classical bits 0 .. n_count-1  measurement output                          |
|                                                                                    |
|    +----------------------------+                                                |
|    | Step 1: H gate on each     |  puts counting register into superposition   |
|    |   counting qubit (0..n-1)  |                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | Step 2: X gate on qubit    |  sets auxiliary register to state |1>         |
|    |   n_count (first aux qubit)|                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | Step 3: for q in           |  controlled c_amod15(a, 2^q)                  |
|    |   0..n_count-1              |  applied on aux register,                    |
|    |   append controlled-U      |  controlled by counting qubit q               |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | Step 4: append qft_dagger  |  inverse QFT on counting register             |
|    |   on counting register     |  QFT = Quantum Fourier Transform              |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | Step 5: measure counting   |  writes to classical bits 0..n_count-1        |
|    |   register                 |                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | transpile + run on          |  backend = aer_simulator                     |
|    |   aer_simulator, shots      |                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|              return counts                                                       |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| C_AMOD15: CONTROLLED PERMUTATION GATE LOGIC  (4-qubit U, then U.control(1))    |
|                                                                                    |
|    Input: a  (must be in [2,4,7,8,11,13]),  power                               |
|                                                                                    |
|    +----------------------------+                                                |
|    | a not in allowed list ?    |----- yes ----> raise ValueError               |
|    +--------------+-------------+                                                |
|                   | no                                                           |
|                   v                                                              |
|    +----------------------------+                                                |
|    | for _iteration in          |  repeat swap pattern 'power' times            |
|    |   range(power)              |                                                |
|    +--------------+-------------+                                                |
|                   |                                                              |
|         +---------+---------+---------+---------+                              |
|         |                   |                   |                                |
|    a in [2,13]         a in [7,8]          a in [4,11]                         |
|         |                   |                   |                                |
|         v                   v                   v                                |
|    swap(0,1)           swap(2,3)           swap(1,3)                           |
|    swap(1,2)           swap(1,2)           swap(0,2)                           |
|    swap(2,3)           swap(0,1)                                                |
|                                                                                    |
|         +-------------------------------------+                                 |
|         |  a in [7, 11, 13]                    |                                |
|         |  X gate on all 4 qubits (q=0..3)     |  fix vs original broken code   |
|         +-------------------------------------+                                 |
|                   |                                                              |
|                   v                                                              |
|    +----------------------------+                                                |
|    | U = U.to_gate()             |  name = "a^power mod 15"                     |
|    | c_U = U.control(1)          |  1 extra control qubit added                 |
|    +--------------+-------------+                                                |
|                   v                                                              |
|              return c_U                                                          |
+----------------------------------------------------------------------------------+

+----------------------------------------------------------------------------------+
| PERIODS_FROM_COUNTS: CONTINUED FRACTIONS DECODE                                 |
|                                                                                    |
|    Input: counts (bitstring -> frequency), n_count, N                          |
|                                                                                    |
|    +----------------------------+                                                |
|    | for output, freq in         |                                                |
|    |   counts.items()            |                                                |
|    +--------------+-------------+                                                |
|                   |                                                              |
|                   v                                                              |
|    +----------------------------+                                                |
|    | decimal = int(output, 2)    |  binary string to integer                    |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | phase = decimal /            |  measured phase, range 0 to 1               |
|    |   (2 ** n_count)             |                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|    +----------------------------+                                                |
|    | frac = Fraction(phase)       |  Fraction limited to denominator <= N        |
|    |   .limit_denominator(N)      |                                                |
|    +--------------+-------------+                                                |
|                   v                                                              |
|         +---------------------+                                                  |
|         | frac.denominator     |----- 0 -----> skip candidate                    |
|         | != 0 ?               |                                                  |
|         +---------+-----------+                                                  |
|                   | yes                                                          |
|                   v                                                              |
|    +----------------------------+                                                |
|    | append (denominator, freq)  |  denominator = candidate period r            |
|    |   to period_candidates      |                                                |
|    +--------------+-------------+                                                |
|                   |  (after all outputs processed)                              |
|                   v                                                              |
|    +----------------------------+                                                |
|    | Counter: sum freq per r      |  weighted[r] += freq                        |
|    +--------------+-------------+                                                |
|                   v                                                              |
|              return weighted (Counter of r -> total freq)                       |
+----------------------------------------------------------------------------------+

evidence_tokens → score each conclusion → normalize → top-N conclusions