microsoft/qdk
Publicmirrored from https://github.com/microsoft/qdkAvailable
source/pip/qsharp/qre/_estimation.py
218lines · modecode
| 1 | # Copyright (c) Microsoft Corporation. |
| 2 | # Licensed under the MIT License. |
| 3 | |
| 4 | from __future__ import annotations |
| 5 | |
| 6 | from typing import cast, Optional, Any |
| 7 | |
| 8 | from .. import telemetry_events |
| 9 | from ._application import Application |
| 10 | from ._architecture import Architecture |
| 11 | from ._qre import ( |
| 12 | _estimate_parallel, |
| 13 | _estimate_with_graph, |
| 14 | _EstimationCollection, |
| 15 | Trace, |
| 16 | ) |
| 17 | from ._trace import TraceQuery, PSSPC, LatticeSurgery |
| 18 | from ._isa_enumeration import ISAQuery |
| 19 | from ._results import EstimationTable, EstimationTableEntry |
| 20 | |
| 21 | |
| 22 | def estimate( |
| 23 | application: Application, |
| 24 | architecture: Architecture, |
| 25 | isa_query: ISAQuery, |
| 26 | trace_query: Optional[TraceQuery] = None, |
| 27 | *, |
| 28 | max_error: float = 1.0, |
| 29 | post_process: bool = False, |
| 30 | use_graph: bool = True, |
| 31 | name: Optional[str] = None, |
| 32 | ) -> EstimationTable: |
| 33 | """ |
| 34 | Estimate the resource requirements for a given application instance and |
| 35 | architecture. |
| 36 | |
| 37 | The application instance might return multiple traces. Each of the traces |
| 38 | is transformed by the trace query, which applies several trace transforms in |
| 39 | sequence. Each transform may return multiple traces. Similarly, the |
| 40 | architecture's ISA is transformed by the ISA query, which applies several |
| 41 | ISA transforms in sequence, each of which may return multiple ISAs. The |
| 42 | estimation is performed for each combination of transformed trace and ISA. |
| 43 | The results are collected into an EstimationTable and returned. |
| 44 | |
| 45 | The collection only contains the results that are optimal with respect to |
| 46 | the total number of qubits and the total runtime. |
| 47 | |
| 48 | Note: |
| 49 | The pruning strategy used when ``use_graph`` is set to True (default) |
| 50 | filters ISA instructions by comparing their per-instruction space, time, |
| 51 | and error independently. However, the total qubit count of a result |
| 52 | depends on the interaction between factory space and runtime: |
| 53 | ``factory_qubits = copies × factory_space`` where copies are determined |
| 54 | by ``count.div_ceil(runtime / factory_time)``. Because of this, an ISA |
| 55 | instruction that is dominated on per-instruction metrics can still |
| 56 | contribute to a globally Pareto-optimal result (e.g., a factory with |
| 57 | higher time may need fewer copies, leading to fewer total qubits). As a |
| 58 | consequence, ``use_graph=True`` may miss some results that |
| 59 | ``use_graph=False`` would find. Use ``use_graph=False`` when completeness of |
| 60 | the Pareto frontier is required. |
| 61 | |
| 62 | Args: |
| 63 | application (Application): The quantum application to be estimated. |
| 64 | architecture (Architecture): The target quantum architecture. |
| 65 | isa_query (ISAQuery): The ISA query to enumerate ISAs from the architecture. |
| 66 | trace_query (TraceQuery): The trace query to enumerate traces from the |
| 67 | application. |
| 68 | max_error (float): The maximum allowed error for the estimation results. |
| 69 | post_process (bool): If True, use the Python-threaded estimation path |
| 70 | (intended for future post-processing logic). If False (default), |
| 71 | use the Rust parallel estimation path. |
| 72 | use_graph (bool): If True (default), use the Rust estimation path that |
| 73 | builds a graph of ISAs and prunes suboptimal ISAs during estimation. |
| 74 | If False, use the Rust estimation path that does not perform any |
| 75 | pruning and simply enumerates all ISAs for each trace. |
| 76 | name (Optional[str]): An optional name for the estimation. If given, this |
| 77 | will be added as a first column to the results table for all entries. |
| 78 | |
| 79 | Returns: |
| 80 | EstimationTable: A table containing the optimal estimation results. |
| 81 | """ |
| 82 | |
| 83 | telemetry_events.on_qre_estimate(post_process=post_process, use_graph=use_graph) |
| 84 | |
| 85 | app_ctx = application.context() |
| 86 | arch_ctx = architecture.context() |
| 87 | |
| 88 | if trace_query is None: |
| 89 | trace_query = PSSPC.q() * LatticeSurgery.q() |
| 90 | |
| 91 | if post_process: |
| 92 | # Enumerate traces with their parameters so we can post-process later |
| 93 | params_and_traces = cast( |
| 94 | list[tuple[Any, Trace]], |
| 95 | list(trace_query.enumerate(app_ctx, track_parameters=True)), |
| 96 | ) |
| 97 | num_traces = len(params_and_traces) |
| 98 | |
| 99 | # Phase 1: Run all estimates in Rust (parallel, fast). |
| 100 | traces_only = [trace for _, trace in params_and_traces] |
| 101 | |
| 102 | if use_graph: |
| 103 | isa_query.populate(arch_ctx) |
| 104 | arch_ctx._provenance.build_pareto_index() |
| 105 | |
| 106 | num_isas = arch_ctx._provenance.total_isa_count() |
| 107 | |
| 108 | collection = _estimate_with_graph( |
| 109 | cast(list[Trace], traces_only), arch_ctx._provenance, max_error, True |
| 110 | ) |
| 111 | isas = collection.isas |
| 112 | else: |
| 113 | isas = list(isa_query.enumerate(arch_ctx)) |
| 114 | |
| 115 | num_isas = len(isas) |
| 116 | |
| 117 | collection = _estimate_parallel( |
| 118 | cast(list[Trace], traces_only), isas, max_error, True |
| 119 | ) |
| 120 | |
| 121 | total_jobs = collection.total_jobs |
| 122 | successful = collection.successful_estimates |
| 123 | summaries = collection.all_summaries # (trace_idx, isa_idx, qubits, runtime) |
| 124 | |
| 125 | # Phase 2: Learn per-trace runtime multiplier and qubit multiplier from |
| 126 | # one sample each: if post_process changes runtime or qubit count it |
| 127 | # will affect the Pareto optimality, but the changes depend only on the |
| 128 | # trace, not on the ISA. |
| 129 | trace_multipliers: dict[int, tuple[float, float]] = {} |
| 130 | trace_sample_isa: dict[int, int] = {} |
| 131 | for t_idx, isa_idx, _q, r in summaries: |
| 132 | if t_idx not in trace_sample_isa: |
| 133 | trace_sample_isa[t_idx] = isa_idx |
| 134 | for t_idx, isa_idx in trace_sample_isa.items(): |
| 135 | params, trace = params_and_traces[t_idx] |
| 136 | sample = trace.estimate(isas[isa_idx], max_error) |
| 137 | if sample is not None: |
| 138 | pre_q = sample.qubits |
| 139 | pre_r = sample.runtime |
| 140 | pp = app_ctx.application.post_process(params, sample) |
| 141 | if pp is not None and pre_r > 0 and pre_q > 0: |
| 142 | trace_multipliers[t_idx] = (pp.qubits / pre_q, pp.runtime / pre_r) |
| 143 | |
| 144 | # Phase 3: Estimate post-pp values and filter to Pareto candidates. |
| 145 | estimated_pp: list[tuple[int, int, int, int]] = ( |
| 146 | [] |
| 147 | ) # (t_idx, isa_idx, est_q, est_r) |
| 148 | for t_idx, isa_idx, q, r in summaries: |
| 149 | mult_q, mult_r = trace_multipliers.get(t_idx, (0.0, 0.0)) |
| 150 | est_q = int(q * mult_q) if mult_q > 0 else q |
| 151 | est_r = int(r * mult_r) if mult_r > 0 else r |
| 152 | estimated_pp.append((t_idx, isa_idx, est_q, est_r)) |
| 153 | |
| 154 | # Build approximate post-pp Pareto frontier to identify candidates. |
| 155 | estimated_pp.sort(key=lambda x: (x[2], x[3])) # sort by qubits, then runtime |
| 156 | approx_pareto: list[tuple[int, int, int, int]] = [] |
| 157 | min_r = float("inf") |
| 158 | for item in estimated_pp: |
| 159 | if item[3] < min_r: |
| 160 | approx_pareto.append(item) |
| 161 | min_r = item[3] |
| 162 | |
| 163 | # Phase 4: Re-estimate and post-process only the Pareto candidates. |
| 164 | pp_collection = _EstimationCollection() |
| 165 | for t_idx, isa_idx, _q, _r in approx_pareto: |
| 166 | params, trace = params_and_traces[t_idx] |
| 167 | result = trace.estimate(isas[isa_idx], max_error) |
| 168 | if result is not None: |
| 169 | pp_result = app_ctx.application.post_process(params, result) |
| 170 | if pp_result is not None: |
| 171 | pp_collection.insert(pp_result) |
| 172 | collection = pp_collection |
| 173 | else: |
| 174 | traces = list(trace_query.enumerate(app_ctx)) |
| 175 | num_traces = len(traces) |
| 176 | |
| 177 | if use_graph: |
| 178 | isa_query.populate(arch_ctx) |
| 179 | arch_ctx._provenance.build_pareto_index() |
| 180 | |
| 181 | num_isas = arch_ctx._provenance.total_isa_count() |
| 182 | |
| 183 | collection = _estimate_with_graph( |
| 184 | cast(list[Trace], traces), arch_ctx._provenance, max_error, False |
| 185 | ) |
| 186 | else: |
| 187 | isas = list(isa_query.enumerate(arch_ctx)) |
| 188 | |
| 189 | num_isas = len(isas) |
| 190 | |
| 191 | # Use the Rust parallel estimation path |
| 192 | collection = _estimate_parallel( |
| 193 | cast(list[Trace], traces), isas, max_error, False |
| 194 | ) |
| 195 | |
| 196 | total_jobs = collection.total_jobs |
| 197 | successful = collection.successful_estimates |
| 198 | |
| 199 | # Post-process the results and add them to a results table |
| 200 | table = EstimationTable() |
| 201 | |
| 202 | table.name = name |
| 203 | |
| 204 | if name is not None: |
| 205 | table.insert_column(0, "name", lambda entry: name) |
| 206 | |
| 207 | table.extend( |
| 208 | EstimationTableEntry.from_result(result, arch_ctx) for result in collection |
| 209 | ) |
| 210 | |
| 211 | # Fill in the stats for this estimation run |
| 212 | table.stats.num_traces = num_traces |
| 213 | table.stats.num_isas = num_isas |
| 214 | table.stats.total_jobs = total_jobs |
| 215 | table.stats.successful_estimates = successful |
| 216 | table.stats.pareto_results = len(collection) |
| 217 | |
| 218 | return table |
| 219 | |