Conceptio › Archive › Google Patents

Google Patentsopen access

Solving computational tasks using quantum computing — Accenture Global Solutions Limited (US11250334B2)

Accenture Global Solutions Limited · Google Patents

Google Patents · Patents · License: Open Access

patent, google patents, intellectual property, US11250334B2, Accenture Global Solutions Limited, Andrew E. Fano, en, 2022

ABSTRACT

Abstract

Methods, systems, and apparatus for solving optimization tasks. In one aspect, a system includes one or more classical processors and one or more quantum computing resources, wherein the one or more classical processors and one or more quantum computing resources are configured to perform operations comprising receiving input data comprising data specifying a computational task to be solved; processing the received input data using a first quantum computing resource to generate data representing a reduced computational task, wherein the reduced computational task has lower dimensionality that the computational task; and processing the data representing the reduced computational task to obtain a solution to the computational task.

Description

BACKGROUND

An optimization task is a task of finding a best solution to a problem from all feasible solutions to the problem. To perform an optimization task, quantum hardware, e.g., a quantum computing device, may be constructed and programmed to encode the solution to a corresponding machine optimization problem into an energy spectrum of a many-body quantum Hamiltonian characterizing the quantum hardware. For example, the solution is encoded in the ground state of the Hamiltonian.

SUMMARY

This specification relates to solving complex computational tasks using a quantum computation engine. The computation engine generates solutions to the complex computational tasks by making nested calls to multiple quantum computing devices. A first call to a quantum computing device may be performed to reduce the complexity of the computational task, e.g., to reduce a number of variables specified by the computational task. A second call to a quantum computing device may be performed to generate a solution to the reduced computational task. The solution to the reduced computational task may be used as an accurate approximation of the solution to the original, complex computational task.

In general, one innovative aspect of the subject matter described in this specification can be implemented in a computer implemented method for solving a computational task using a system including multiple computing resources, where the multiple computing resources comprise at least one quantum computing resource, the method including the actions of: receiving input data comprising data specifying the computational task to be solved; processing the received input data using a first quantum computing resource to generate data representing a reduced computational task, wherein the reduced computational task has lower dimensionality that the computational task; and processing the data representing the reduced computational task to obtain a solution to the computational task.

Other implementations of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods. A system of one or more computers can be configured to perform particular operations or actions by virtue of having software, firmware, hardware, or a combination thereof installed on the system that in operation causes or cause the system to perform the actions. One or more computer programs can be configured to perform particular operations or actions by virtue of including instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions.

The foregoing and other implementations can each optionally include one or more of the following features, alone or in combination. In some implementations the dimensionality of the computational task is based on a number of variables specified by the computational task.

In some implementations processing the received input data using the first quantum computing resource to generate data representing a reduced computational task comprises performing principal component analysis.

In some implementations the first quantum computing resource comprises a quantum gate computer or a quantum annealer.

In some implementations the generated solution to the computational task is obtained from a second quantum computing resource.

In some implementations the second quantum computing resource comprises a (i) quantum gate computer, (ii) quantum annealer, or (iii) quantum simulator.

In some implementations the generated solution to the computational task is obtained from a classical computing resource.

In some implementations the computational task is an optimization task.

In some implementations the input data comprises (i) data specifying the optimization task to be solved, and (ii) data specifying task objectives for solving the optimization task, comprising one or more local task objectives and one or more global task objectives.

In some implementations processing the data representing the reduced optimization task to obtain a solution to the optimization task comprises: processing the received input data to obtain one or more initial solutions to the optimization task based on the local task objectives; and processing the generated one or more initial solutions to generate a global solution to the optimization task based on the global task objectives.

The subject matter described in this specification can be implemented in particular ways so as to realize one or more of the following advantages.

Some computational tasks are too complex to solve using classical computing devices. For example, some current cryptographic protocols for secure data transmission such as RSA or Diffie-Hellman rely on the impracticality of performing integer factorization for sufficiently large integers using classical computers. In some cases, quantum computing devices may be used to solve such computational tasks. For example, according to Shor's algorithm, quantum computing devices may be used to factor integers of arbitrary size in polynomial time.

Alternatively or in addition, for some computational tasks, quantum computing devices may offer an increase in computational speed compared to classical devices. For example, quantum computers may achieve a polynomial increase in speed for tasks such as database searching or evaluating NAND trees. As another example, quantum annealers may achieve a computational increase in speed compared to classical annealers for some optimization tasks. For example, determining a global minimum or maximum of a complex manifold is an extremely challenging task. If a mapping exists for such an optimization task from the classical domain to the quantum domain appropriate for an available quantum annealer, using the quantum annealer to solve the optimization task can be an accurate and efficient alternative to using classical devices.

In some cases, however, computational tasks may be too complex or high-dimensional to solve using classical or quantum computing resources. A quantum computation engine, as described in this specification, uses nested calls to quantum computing devices to solve such computational tasks. First calls to quantum computing devices may be used to transform computational tasks into computational tasks with lower dimensionality and/or lower complexity. Further calls to classical or quantum computing resources may be used to solve the transformed computational tasks and generate approximate solutions to the computational tasks. In this manner, the quantum computation engine may be used to solve computational tasks that are intractable to other computation engines.

In addition, the quantum computation engine described in this specification uses both classical and quantum computing devices to solve computational tasks, thus increasing the computational capabilities of the computation engine compared to computation engines that do not include both classical and quantum computing devices. For example, typically the number of variables that can be efficiently described by a purely classical system is restricted. A quantum computation engine, as described in this specification, combines quantum technology with classical technology in such a manner that allows the system to describe an increased number of variables compared to a classical system. Therefore, solutions to computational tasks generated by the quantum computation engine may be more accurate than solutions generated by a classical optimization system. In addition, the quantum computation engine may be applied to a wider range of computational tasks than a classical system.

A quantum computation engine, as described in this specification, may be used to solve optimization tasks from a wide range of applications, including but not limited to machine learning, sampling/Monte Carlo, information security, pattern recognition, image analysis, systems design, precision agriculture, scheduling, network design and bioinformatics.

In some implementations, a quantum computation engine, as described in this specification, may be able to process sparse inputs or linear forward computations during an execution of a dimensionality reduction process.

The details of one or more implementations of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 depicts an example quantum computation engine.

FIG. 2 depicts an example global computation engine.

FIG. 3 is a flow diagram of an example process for generating a solution to a computational task.

Like reference numbers and designations in the various drawings indicate like elements.

DETAILED DESCRIPTION

This specification describes a quantum computation engine that uses multiple calls to quantum computing resources to solve complex computational tasks. Complex computational tasks include computational tasks that are too difficult for classical or quantum computing resources to solve, e.g., computational tasks with an intractable number of task variables.

A first call to a first quantum computing resource is used to reduce the complexity of the computational task, e.g., to reduce the number of variables included the computational task. The first quantum computing resource may be configured to perform quantum algorithms such as quantum machine learning algorithms, clustering, pattern-matching or principal component analysis to reduce the complexity of the computational task. In some cases, the first quantum computing resource may be a quantum annealer. In other cases, the first quantum computing resource may be a quantum computer, e.g., a quantum circuit.

Subsequent calls to a second computing resource is used to solve the computational task. Since the complexity of the reduced computational task is smaller than the complexity of the computational task as received by the system, the second computing resource may efficiently perform the reduced computational task to generate a solution that may be used as an approximate solution to the original computational task. In some cases the reduced computational task may be performed using a second quantum computing device. In other cases the reduced computational task may be small enough/practical enough to solve using classical computing resources.

Example Operating Environment

FIG. 1 depicts an example quantum computation engine 100 . The quantum computation engine 100 is an example of a system implemented as computer programs on one or more classical or quantum computing devices in one or more locations, in which the systems, components, and techniques described below can be implemented. Components of the quantum computation engine 100 may be interconnected by a digital and/or quantum data communication network.

The quantum computation engine 100 is configured to receive as input data representing a computational task to be solved, e.g., input data 102 . For example, in some cases the quantum computation engine 100 may be configured to solve multiple computational tasks, and the input data 102 may be data that specifies one of the multiple computational tasks. The input data 102 representing the computational task to be solved may specify one or more properties of the computational task, parameters associated with the computational task, e.g., parameters over which an objective function representing a computational task is to be optimized, and one or more values of the parameters. Example computational tasks include, but are not limited to, optimization tasks, decision problems, counting problems or function problems. In some cases the input data 102 may include static input data and dynamic input data, e.g., real-time input data.

For example, the input data 102 may be data that represents the task of optimizing the design of a water network, e.g., to improve the amount of water delivered by the network, or to reduce the amount of water wastage in the network. In this example, the input data 102 may include static input data representing one or more properties of the water network, e.g., a total number of available water pipes, a total number of available connecting nodes or a total number of available water tanks. In addition, the input data 102 may include data representing one or more parameters associated with the computational task, e.g., level of water pressure in each pipe, level of water pressure at each connecting node, height of water level in each water tank, concentration of chemicals in the water throughout the network, water age or water source. Furthermore, the input data 102 may include dynamic input data representing one or more current properties or values of parameters of the water network, e.g., a current number of water pipes in use, a current level of water pressure in each pipe, a current concentration of chemicals in the water, or a current temperature of the water.

The computational task represented by the input data 102 may be associated with one or more measures of computational task dimensionality or complexity. For example, the dimensionality of the computational task may be measured based on a number of variables specified by the computational task. As another example, the complexity of the computational task may be measured based on an amount of computational resources, e.g., classical resources, needed to solve the task, such as time and storage. Other example complexity measures include an amount of communication required to solve the task, number of gates in a circuit used to solve the task, or number of processors used to solve the task

In some implementations, the input data 102 may further include data specifying one or more task objectives associated with

BACKGROUND

SUMMARY

In some implementations the first quantum computing resource comprises a quantum gate computer or a quantum annealer.

In some implementations the generated solution to the computational task is obtained from a second quantum computing resource.

In some implementations the second quantum computing resource comprises a (i) quantum gate computer, (ii) quantum annealer, or (iii) quantum simulator.

In some implementations the generated solution to the computational task is obtained from a classical computing resource.

In some implementations the computational task is an optimization task.

The subject matter described in this specification can be implemented in particular ways so as to realize one or more of the following advantages.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 depicts an example quantum computation engine.

FIG. 2 depicts an example global computation engine.

FIG. 3 is a flow diagram of an example process for generating a solution to a computational task.

Like reference numbers and designations in the various drawings indicate like elements.

DETAILED DESCRIPTION

Example Operating Environment

In some implementations, the input data 102 may further include data specifying one or more task objectives associated with the computational task. The task objectives may include local task objectives and global task objectives. Local task objectives may include local targets to be considered when solving the computational task, e.g., local objectives of a solution to the computational task. For example, local objectives may include constraints on values of subsets of computational task variables. Global task objectives may include global targets to be considered when solving the computational task, e.g., global objectives of a solution to the computational task.

For example, continuing the above example of the task of optimizing a water network, the input data 102 may further include data specifying local task objectives such as a constraint on the concentration of chemicals in the water, e.g., constraining the chemical concentration to between 0.2% and 0.5%, and on the number of water pipes in use, e.g., constraining the total number of water pipes to less than 1000. Another example local task objective may be to optimize a particular portion of the water network. In addition, the input data 102 may further include data specifying global task objectives such as one or more global targets, e.g., a target of keeping water wastage to below 2% or a target of distributing at least 10 million gallons of water per day.

In other implementations, data specifying one or more task objectives associated with the computational task may be stored in the quantum computation engine 100 , e.g., in task objective data store 112 . For example, as described above, the quantum computation engine 100 may be configured to solve multiple computational tasks and the input data 102 may be data that specifies one of the multiple computational tasks. In this example, the quantum computation engine 100 may be configured to store task objectives corresponding to each computational task that it is configured to perform. For convenience, data specifying one or more task objectives associated with the computational task is described as being stored in task objective data store 112 throughout the remainder of this document.

The quantum computation engine 100 is configured to process the received input data 102 to generate output data 104 . In some implementations, the generated output data 104 may include data representing a global solution to the computational task specified by the input data 102 , e.g., a global solution to the computational task based on one or more global task objectives 112 b . In some cases, the generated output data 104 may include data representing an approximate global solution to the computational task specified by the input data 102 . For example, as described in more detail below and with reference to FIG. 3 , in some cases the computational task represented by the input data 102 may be too complex or high-dimensional for available computing resources to solve. In these cases, the quantum computation engine 100 may be configured to process the received input data 102 to generate data representing a reduced computational task to be solved, and may process this data to generate output data 104 . Processing received input data representing a computational task to be solved and one or more objectives for solving the computational task to generate output data representing a global solution to the computational task is described in more detail below with reference to FIGS. 2 and 3 .

In other implementations or in addition, the output data 104 may include data representing one or more local solutions to the computational task, e.g., one or more initial solutions to the computational task that are based on local task objectives 112 a and global task objectives 112 b . Local solutions to the computational task may include solutions to sub-tasks of the computational task. For example, local solutions may include solutions that are optimal over a subset of the parameters associated with the computational task, e.g., where the subset is specified by the local task objectives 112 a . That is, local solutions may include solutions that are optimal over a subspace, or local space, of a global search space of the computational task. For example, a local space may be the result of a projection of a multi-dimensional spline representing the global search space to a two-dimensional base space.

As another example, in cases where the computational task is a separable task, e.g., a task that may be written as the sum of multiple sub-tasks, local solutions may include optimal solutions to each of the sub-tasks in the sum of sub-tasks, e.g., where the sub-tasks are specified by the local task objectives 112 a.

For example, continuing the above example of the task of optimizing a water network, the output data 104 may include data representing a globally optimal configuration (with respect to global task objectives, e.g., wastage targets and productivity targets) of the above described parameters associated with the water network optimization task. Alternatively, or in addition, the output data 104 may include data representing multiple local solutions to the water network optimization task, e.g., data specifying an optimal number of water pipes to use, an associated water pressure in each pipe, or a concentration of chemicals in the water flowing through the network. In some implementations, parameter values specified by local solutions may be the same as parameter values specified by a global solution. In other implementations, parameter values specified by local solutions may differ from parameter values specified by a global solution, e.g., a local solution may suggest a chemical concentration of 0.4%, whereas a global solution may suggest a chemical concentration of 0.3%.

The output data 104 may be used to initiate one or more actions associated with the computational task specified by the input data 102 , e.g., actions 138 . For example, continuing the above example of the task of optimizing a water network, the output data 104 may be used to adjust one or more parameters in the water network, e.g., increase or decrease a current water chemical concentration, increase or decrease a number of water pipes in use, or increase or decrease one or more water pipe pressures.

Optionally, the quantum computation engine 100 may include an integration layer 114 and a broker 136 . The integration layer 114 may be configured to manage received input data, e.g., input data 102 . For example, the integration layer 114 may manage data transport connectivity, manage data access authorization, or monitor data feeds coming into the system 100 .

The broker 136 may be configured to receive output data 104 from the quantum computation engine and to generate one or more actions to be taken, e.g., actions 138 . The actions may include local actions, e.g., adjustments to a subset of computation parameters, which contribute towards achieving local and global targets of the computational task.

The quantum computation engine 100 includes a global computation engine 106 , which in turn includes a local computation engine 108 . The global computation engine 106 is configured to receive the input data 102 and task objectives 112 for the computational task specified by the input data 102 , and to provide the input data 102 and one or more local task objectives 112 a to the local computation engine 108 .

The local computation engine 108 is configured to process the received data to obtain one or more initial solutions to the computational task based on the one or more local task objectives 112 a , e.g., one or more local solutions to the computational task.

In some implementations, the local computation engine 108 may be configured to process received data using one or more computing resources included in the local computation engine 108 or otherwise included in the quantum computation engine 100 . In other implementations, the local computation engine may be configured to process received data using one or more external computing resources, e.g., additional computing resources 110 a - 110 d . For example, the local computation engine 108 may be configured to analyze the received input data 102 representing the computational task to be solved and the data representing corresponding local task objectives 112 a , and outsource one or more computations associated with solving the computational task based on the local task objectives 112 a to the additional computing resources 110 a - 110 d.

The additional computing resources 110 a - 110 d may include multiple quantum annealer computing resources, e.g., quantum annealers 110 a . A quantum annealer is a device configured to perform quantum annealingâa procedure for finding the global minimum of a given objective function over a given set of candidate states using quantum tunneling. Quantum tunneling is a quantum mechanical phenomenon where a quantum mechanical system overcome localized barriers in the energy landscape which cannot be overcome by classically described system. An example quantum annealer is described in more detail below with reference to FIG. 2 . In some implementations, one or more of the quantum annealers 110 a may be configured to perform dimensionality reduction algorithms, e.g., principal component analysis or independent component analysis, and/or complexity reduction algorithms, e.g., circuit minimization or logic optimization algorithms.

The additional computing resources 110 a - 110 d may include one or more quantum gate processors, e.g., quantum gate processor 110 b . A quantum gate processor includes one or more quantum circuits, i.e., models for quantum computation in which a computation is performed using a sequence of quantum logic gates, operating on a number of qubits (quantum bits). In some implementations, one or more of the quantum gate processors 110 b may be configured to perform dimensionality reduction algorithms, e.g., principal component analysis or independent component analysis, and/or complexity reduction algorithms, e.g., circuit minimization or logic optimization algorithms.

The additional computing resources 110 a - 110 d may include one or more quantum simulators, e.g., quantum simulator 110 c . A quantum simulator is a quantum computer that may be programmed to simulate other quantum systems and their properties. Example quantum simulators include experimental platforms such as systems of ultracold quantum gases, trapped ions, photonic systems or superconducting circuits.

The additional computing resources 110 a - 110 d may include one or more classical processors, e.g., classical processor 110 d . In some implementations, the one or more classical processors, e.g., classical processor 110 d , may include supercomputers, i.e., computers with high levels of computational capacity. For example, the classical processor 110 d may represent a computational system with a large number of processors, e.g., a distributed computing system or a computer cluster.

The quantum computation engine 100 includes a router 132 that is configured to determine which, if any, computations to outsource to the additional computing resources 110 a - 110 d . Determining which, if any, computations to outsource to the additional computing resources 110 a - 110 d is dependent on multiple factors, including the type of computations, current availability of the additional computing resources 110 a - 110 d , cost of running the additional computing resources 110 a - 110 d , and the type of computational task. For example, in some cases an additional computing resource may be configured to perform only a limited number of specific computational tasks or types of computational tasks.

As described briefly above, in some implementations the dimensionality and/or complexity of the computational task represented by the input data 102 may be too high to enable the computational task to be efficiently solved using the additional computing resources 110 a - 110 d . For example, to solve the computational task in an acceptable time, e.g., a predetermined finite time, the quantum computation engine 100 may require access to one or more classical computing resources, e.g., classical computing resources 110 d , that operate using a minimum number of bits, or to one or more quantum computing resources, e.g., quantum computing resources 110 a - 110 c , that operate using a minimum number of qubits. However, in some cases the number of bits or qubits included in the additional computing resources 110 a - 110 d may be limited and not sufficient to solve the computational task in the acceptable time. For example, when performing phase estimation algorithms, eigenvalues and eigenvectors of the unitary operator describing the unitary evolution of a quantum state can be estimated to accuracy oÌ§ by applying a quantum phase algorithm for a time t=O(oÌ§ â1 ), and requires n=O(1/oÌ§ 3 ) copies of the state Ï.

As another example, the computational task may be an intractable taskâthat is a task that may be solved in theory, but which in practice takes too long for its solution to be useful. Example intractable tasks include NP computational tasks (under the assumption that NP is not equal to P).

In these implementations, the global computation engine 106 may be configured to determine that the dimensionality and/or complexity of the computational task represented by the input data 102 is too high to enable the computational task to be efficiently solved using the additional computing resources 110 a - 110 d or that solution of the task could benefit from a reduction in complexity. The global computation engine 106 may then instruct the router 132 to determine which additional computing resource 110 a - 110 d to provide the received input data 102 to, and may provide the received input data 102 to the determined computing resource together with data specifying that the additional computing resource is to perform a dimensionality or complexity reduction algorithm on the input data 102 . For example, the router 132 may be configured to determine that the input data 102 be provided to a quantum annealer, e.g., one of quantum annealers 110 a . The quantum annealer may then perform a dimensionality or complexity reduction algorithm, e.g., principal component analysis, on the input data 102 . In some cases the data specifying that the additional computing resource is to perform a dimensionality or complexity reduction algorithm on the input data 102 may indicate a target dimensionality or complexity, e.g., a predetermined dimensionality or complexity chosen based on one or more of (i) the computational task to be solved, (ii) the computational capabilities of the additional computing resources 110 a - 110 d , and (iii) the received input data 102 . In some cases a Jaynes-Cummings model may be used to determine a target dimensionality.

The router may be further configured to receive, from the quantum computing resource, data representing a reduced computational task. The reduced computational task may be a computational task that has lower dimensionality than the computational task. For example, the reduced computational task may specify a lower number of variables than the original computational task. Alternatively, or in addition, the reduced computational task may be a computational task that has lower complexity than the computational task. For example, solving the reduced computational task may require less computational resources than solving the original computational task, less communication, fewer logic gates or fewer processors. Data representing the reduced computational task may be provided to the global computation engine 106 for processing, as described above.

Optionally, the quantum computation engine 100 may include a monitoring module 128 . The monitoring module 128 is configured to monitor interactions between and transactions to and from the one or more additional computing resources 110 a - d . For example, the monitoring module 128 may be configured to detect failed or stuck calls to one or more of the additional computing resources 110 a - d . Example failures that can cause a call to one or more of the additional computing resources 110 a - d to fail or get stuck include issues with a transport layer included in the system 100 , i.e., issues with data being moved through the cloud, security login failures, or issues with the additional computing resources 110 a - d themselves such as performance or availability of the additional computing resources 110 a - d . The monitoring module 128 may be configured to process detected failed or stuck calls to one or more of the additional computing resources 110 a - d and determine one or more corrective actions to be taken by the system 100 in response to the failed or stuck calls. Alternatively, the monitoring module 128 may be configured to notify other components of the system 100 , e.g., the global computation engine 106 or router 132 , of detected failed or stuck calls to one or more of the additional computing resources 110 a - d.

For example, if one or more computations are outsourced to a particular quantum computing resource, and the particular quantum computing resource suddenly becomes unavailable or is processing outsourced computations too slowly, the monitoring module 128 may be configured to notify relevant components of the system 100 , e.g., the router 132 or global computation engine 106 . The monitoring system 128 may be further configured to provide the relevant components of the system with a suggested corrective action, e.g., instructing the system 100 to outsource the computation to a different computing resource or to retry the computation using the same computing resource. Generally, the suggested corrective actions may include actions that keep the system 100 successfully operating in real time, e.g., even when resource degradations outside of the system 100 are occurring.

Optionally, the quantum computation engine 100 may include a security component 130 . The security component 130 may be configured to perform operations relating to the security of the system 100 . Example operations include, but are not limited to, preventing system intrusions, detecting system intrusions, providing authentication to external systems, encrypting data received by and output by the system 100 , and preventing and/or remedying denial of service (DoS).

The local computation engine 108 is configured to provide the one or more obtained initial solutions to the computational task to the global computation engine 106 . The global computation engine 106 is configured to process the received one or more initial solutions to the computational task using a quantum computing resource to generate a global solution to the computational task based on the global task objectives 112 b . Generating a global solution to a computational task based on one or more initial solutions to the computational task and on one or more global task objectives is described in more detail below with reference to FIGS. 2, 3 and 4 .

Optionally, the quantum computation engine 100 may include a subgraph module 122 . The subgraph module 122 may be configured to partition a computational task into multiple sub-tasks. For example, the subgraph module 122 may be configured to analyze data specifying a computational task to be solved, and to map the computational task to multiple minimally connected subgraphs. The minimally connected subgraphs may be provided to the

CLAIMS

Claims ( 14 )

What is claimed is:

1. A computer implemented method for solving a computational task using a system including multiple computing resources, wherein the computational task comprises an optimization task and the multiple computing resources comprise at least one quantum computing resource, the method comprising:

receiving input data comprising data specifying the computational task to be solved, wherein the computational task is associated with a task dimensionality and a complexity based on an amount of classical or quantum computational resources required to solve the task;

identifying one or more available classical or quantum computing resources;

determining, based on the associated task dimensionality and complexity, whether the computational task is intractable for the one or more available classical or quantum computing resources, comprising determining whether a number of bits or qubits included in the one or more available classical or quantum computing resources are insufficient to solve the computational task in an acceptable time;

in response to determining that the computational task is intractable for the one or more available classical or quantum computing resources, instructing a first quantum computing resource to perform i) dimensionality reduction algorithm and ii) a circuit minimization algorithm, logic optimization algorithm or Hadamard gate reduction algorithm on the input data, comprising providing the input data to the first quantum computing resource for processing;

processing the received input data using the first quantum computing resource to generate data representing a reduced computational task, wherein the processing comprises performing i) a dimensionality reduction algorithm and ii) a circuit minimization algorithm, logic optimization algorithm or Hadamard gate reduction algorithm on the input data using the first quantum computing resource, and wherein the reduced computational task has lower dimensionality and lower task complexity than the computational task; and

processing the data representing the reduced computational task using an available classical or quantum computing resource to obtain a solution to the reduced computational task, wherein i) the solution to the reduced computational task comprises an approximate solution to the computational task and ii) processing the data representing the reduced computational task to obtain a solution to the reduced computational task uses a smaller number of classical or quantum logic gates than the number of classical or quantum logic gates required to solve the computational task.

2. The method of claim 1 , wherein the dimensionality of the computational task is based on a number of variables specified by the computational task.

3. The method of claim 1 , wherein processing the received input data using the first quantum computing resource to generate data representing a reduced computational task comprises performing principal component analysis.

4. The method of claim 1 , wherein the first quantum computing resource comprises a quantum gate computer or a quantum annealer.

5. The method of claim 1 , wherein the input data comprises (i) data specifying the optimization task to be solved, and (ii) data specifying task objectives for solving the optimization task, comprising one or more local task objectives and one or more global task objectives.

6. The method of claim 5 , wherein processing the data representing the reduced computational task using an available classical or quantum computing resource to obtain a solution to the optimization task comprises:

processing the received input data to obtain one or more initial solutions to the optimization task based on the local task objectives; and

processing the generated one or more initial solutions to generate a global solution to the optimization task based on the global task objectives.

7. The method of claim 1 , wherein the reduced computational task requires less classical or quantum computational resources to solve compared to the computational task.

8. A system of multiple computing resources, comprising:

one or more classical processors;

one or more quantum computing resources;

wherein the one or more classical processors and one or more quantum computing resources are configured to perform operations comprising:

identifying one or more available classical or quantum computing resources;

9. The system of claim 8 , wherein the dimensionality of the computational task is based on a number of variables specified by the computational task.

10. The system of claim 8 , wherein processing the received input data using the first quantum computing resource to generate data representing a reduced computational task comprises performing principal component analysis.

11. The system of claim 8 , wherein the first quantum computing resource comprises a quantum gate computer or a quantum annealer.

12. The system of claim 8 , wherein the input data comprises (i) data specifying the optimization task to be solved, and (ii) data specifying task objectives for solving the optimization task, comprising one or more local task objectives and one or more global task objectives.

13. The system of claim 12 , wherein processing the data representing the reduced computational task using an available classical or quantum computing resource to obtain a solution to the optimization task comprises:

processing the received input data to obtain one or more initial solutions to the optimization task based on the local task objectives; and

processing the generated one or more initial to generate a global solution to the optimization task based on the global task objectives.

14. The system of claim 8 , wherein the reduced computational task requires less classical or quantum computational resources to solve compared to the computational task.

US15/491,810

2017-04-19

Solving computational tasks using quantum computing

Active

2039-05-29

US11250334B2

( en )

Priority Applications (2)

Application Number

Priority Date

Filing Date

Title

US15/491,810

US11250334B2

( en )

2017-04-19

Solving computational tasks using quantum computing

EP18161884.4A

EP3392808B1

( en )

2017-04-19

2018-03-15

Solving computational tasks using quantum computing

Applications Claiming Priority (1)

Application Number

Priority Date

Filing Date

Title

US15/491,810

US11250334B2

( en )

2017-04-19

Solving computational tasks using quantum computing

Publications (2)

Publication Number

Publication Date

US20180307988A1

US20180307988A1 ( en )

2018-10-25

US11250334B2

true

US11250334B2 ( en )

2022-02-15

Family

ID=61683606

Family Applications (1)

Application Number

Title

Priority Date

Filing Date

US15/491,810

Active

2039-05-29

US11250334B2

( en )

2017-04-19

Solving computational tasks using quantum computing

Country Status (2)

Country

Link

( 1 )

US11250334B2

( en )

( 1 )

EP3392808B1

( en )

Cited By (3)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20210406752A1

( en )

2017-06-19

2021-12-30

Rigetti & Co, Inc.

Distributed Quantum Computing System

RU2826431C1

( en )

2024-03-19

2024-09-10

Method and system for distributing computational tasks in cloud environment

US20240338213A1

( en )

2021-04-21

2024-10-10

Origin Quantum Computing Technology (Hefei) Co., Ltd

Quantum computing platform adaptation method and apparatus, and quantum computer operating system

Families Citing this family (27)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

EP3369048A4

( en )

2015-10-27

2018-10-31

D-Wave Systems Inc.

Systems and methods for degeneracy mitigation in a quantum processor

US11170137B1

( en )

2017-11-15

2021-11-09

Amazon Technologies, Inc.

Cloud-based simulation of quantum computing resources

US11270220B1

( en )

2017-11-15

2022-03-08

Amazon Technologies, Inc.

Service for managing quantum computing resources

US10817337B1

( en )

2017-11-15

2020-10-27

Amazon Technologies, Inc.

Cloud-based access to quantum computing resources

US10803395B2

( en )

2018-06-07

2020-10-13

International Business Machines Corporation

Quantum computations of classical specifications

US11122136B2

( en )

2018-10-22

2021-09-14

Red Hat, Inc.

Quantum payload service for facilitating communications between a quantum computing system and classical computing systems

WO2020150156A1

( en )

2019-01-17

2020-07-23

D-Wave Systems, Inc.

Systems and methods for hybrid algorithms using cluster contraction

WO2020210536A1

( en )

2019-04-10

2020-10-15

D-Wave Systems Inc.

Systems and methods for improving the performance of non-stoquastic quantum devices

CN110069385A

( en )

2019-04-26

2019-07-30

æµåæµªæ½®é«æ°ç§ææèµåå±æéå¬å¸

Quantum cloud monitoring system and method based on Internet of Things

US11309974B2

( en )

2019-05-09

2022-04-19

Red Hat, Inc.

Quantum channel routing utilizing a quantum channel measurement service

US11494532B2

( en )

2019-06-17

2022-11-08

International Business Machines Corporation

Simulation-based optimization on a quantum computer

US20210012233A1

( en )

2019-07-11

2021-01-14

International Business Machines Corporation

Adaptive compilation of quantum computing jobs

CN110825375B

( en )

2019-10-12

2022-12-06

åè¥æ¬æºéåè®¡ç®ç§ææéè´£ä»»å¬å¸

Quantum program conversion method and device, storage medium and electronic device

US11704715B2

( en )

2019-11-27

2023-07-18

Amazon Technologies, Inc.

Quantum computing service supporting multiple quantum computing technologies

EP4722916A2

( en )

2019-11-27

2026-04-08

Amazon Technologies, Inc.

Quantum computing service supporting multiple quantum computing technologies

US11605016B2

( en )

2019-11-27

2023-03-14

Amazon Technologies, Inc.

Quantum computing service supporting local execution of hybrid algorithms

US11605033B2

( en )

2019-11-27

2023-03-14

Amazon Technologies, Inc.

Quantum computing task translation supporting multiple quantum computing technologies

CN111242306B

( en )

2020-01-22

2021-07-20

åäº¬ç¾åº¦ç½è®¯ç§ææéå¬å¸

Method, apparatus, electronic device, and computer-readable storage medium for quantum principal component analysis

US12299593B2

( en )

2020-02-05

2025-05-13

D-Wave Systems Inc.

Systems and methods for optimizing annealing parameters

WO2021195783A1

( en )

2020-04-03

2021-10-07

The University Of British Columbia

Method of simulating a quantum computation, system for simulating a quantum computation, method for issuing a computational key, system for issuing a computational key

US11687817B2

( en )

2020-09-28

2023-06-27

Cognizant Technology Solutions India Pvt. Ltd.

System and method for providing data computation via quantum computers

GB2601996A

( en )

2020-12-09

2022-06-22

Mastercard International Inc

Network optimisation

US20230252501A1

( en )

2021-04-16

2023-08-10

Strong Force Vcn Portfolio 2019, Llc

Control-Tower-Based Digital Product Network System

US11907092B2

( en )

2021-11-12

2024-02-20

Amazon Technologies, Inc.

Quantum computing monitoring system

US12217090B2

( en )

2021-11-12

2025-02-04

Amazon Technologies, Inc.

On-demand co-processing resources for quantum computing

US12265853B2

( en )

2022-05-19

2025-04-01

The Boeing Company

Hybrid-computing resource optimization

US12505366B2

( en )

2022-11-30

2025-12-23

Nvidia Corporation

Simulating quantum computing circuits using Kronecker factorization

Citations (12)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20060282236A1

( en )

2002-08-14

2006-12-14

Axel Wistmuller

Method, data processing device and computer program product for processing data

US20070087756A1

( en )

2005-10-04

2007-04-19

Hoffberg Steven M

Multifactorial optimization system and method

WO2008028290A1

( en )

2006-09-06

2008-03-13

D-Wave Systems Inc.

Method and system for solving integer programming and discrete optimization problems using analog processors

US20090070402A1

( en )

2007-09-11

2009-03-12

Geordie Rose

Systems, methods, and apparatus for a distributed network of quantum computers

US20110238378A1

( en )

2007-12-12

2011-09-29

Allen Edward H

Computer systems and methods for quantum verification and validation

US8117119B2

( en )

2007-04-03

2012-02-14

General Mortgage Finance Corp.

Systems and methods of trading closed loans, debt, and other financial obligations

US20140187427A1

( en )

2011-07-06

2014-07-03

D-Wave Systems Inc.

Quantum processor based systems and methods that minimize an objective function

US20140358852A1

( en )

2013-05-29

2014-12-04

Codership Oy

Method of synchronizing data within database clusters

US20150006443A1

( en )

2013-06-28

2015-01-01

D-Wave Systems Inc.

Systems and methods for quantum processing of data

US20150349780A1

( en )

2014-05-29

2015-12-03

Northrop Grumman Systems Corporation

Hybrid quantum circuit assembly

US20170073756A1

( en )

2014-03-13

2017-03-16

Sequenom, Inc.

Methods and processes for non-invasive assessment of genetic variations

US20170104493A1

( en )

2015-10-07

2017-04-13

Kabushiki Kaisha Toshiba

Quantum computation apparatus and quantum computation method

2017

2017-04-19

US15/491,810

patent/US11250334B2/en

active

Active

2018

2018-03-15

EP18161884.4A

patent/EP3392808B1/en

active

Active

Patent Citations (12)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20060282236A1

( en )

2002-08-14

2006-12-14

Axel Wistmuller

Method, data processing device and computer program product for processing data

US20070087756A1

( en )

2005-10-04

2007-04-19

Hoffberg Steven M

Multifactorial optimization system and method

WO2008028290A1

( en )

2006-09-06

2008-03-13

D-Wave Systems Inc.

Method and system for solving integer programming and discrete optimization problems using analog processors

US8117119B2

( en )

2007-04-03

2012-02-14

General Mortgage Finance Corp.

Systems and methods of trading closed loans, debt, and other financial obligations

US20090070402A1

( en )

2007-09-11

2009-03-12

Geordie Rose

Systems, methods, and apparatus for a distributed network of quantum computers

US20110238378A1

( en )

2007-12-12

2011-09-29

Allen Edward H

Computer systems and methods for quantum verification and validation

US20140187427A1

( en )

2011-07-06

2014-07-03

D-Wave Systems Inc.

Quantum processor based systems and methods that minimize an objective function

US20140358852A1

( en )

2013-05-29

2014-12-04

Codership Oy

Method of synchronizing data within database clusters

US20150006443A1

( en )

2013-06-28

2015-01-01

D-Wave Systems Inc.

Systems and methods for quantum processing of data

US20170073756A1

( en )

2014-03-13

2017-03-16

Sequenom, Inc.

Methods and processes for non-invasive assessment of genetic variations

US20150349780A1

( en )

2014-05-29

2015-12-03

Northrop Grumman Systems Corporation

Hybrid quantum circuit assembly

US20170104493A1

( en )

2015-10-07

2017-04-13

Kabushiki Kaisha Toshiba

Quantum computation apparatus and quantum computation method

Non-Patent Citations (12)

* Cited by examiner, â Cited by third party

Title

âarxiv.comâ [online]. " A Tutorial on Principal Component Analysis, " Apr. 3, 2014, [Retrieved Sep. 21, 2017], Retrieved from the Internet: URL< https://arxiv.org/abs/1404.1100# >, 2 pages.

âarxiv.orgâ [online]. " Quantum principal component analysis, " Jul. 1, 2013, [Retrieved Sep. 21, 2017], Retrieved from the Internet: URL< https://arxiv.org/abs/1307.0401 >, 2 pages.

âiopscience.iop.orgâ [online]. " Quantum discriminant analysis for dimensionality reduction and classification, " Jul. 6, 2016, [Retrieved Sep. 21, 2017], Retrieved from the Internet: URL< http://iopscience.iop.org/article/10.1088/1367-2630/18/7/073011/meta>, 11 pages.

âQuantum principal component analysisâ: Lloyd, 2014, Nature Physics, pp. 631-633.

âQuantum Recurrent Neural Networks for Filteringâ: Ahamed, 2009.

âReversible artihmetic coding for quantum data compressionâ: Chuang, 2000, IEEE, pp. 1104-1116 (Year: 2000).

" Quantum Computer Science ": Mermin, 2007, Cambridge University Press.

Cong et al., " Quantum discriminant analysis for dimensionality reduction and classification, " New Journal of Physics, Jul. 6, 2016, 18:7 1-9.

EP International Search Report and Written Opinion in European Application No. 18161884.4, dated Sep. 3, 2018, 8 pages.

Harrow et al., " Quantum algorithm for solving linear systems of equations, " arXiv.0811.3171v3, Cornell University Library, Sep. 30, 2009, 15 pages.

Hashizume et al., " Singular-value decomposition using quantum annealing, " Physical Review E, Aug. 12, 2015, 92:2 6 pages.

Scott Aaronson, " Quantum Machine Learning Algorithms: Read the Fine Print, " 2015, 5 pages.

Cited By (7)

* Cited by examiner, â Cited by third party

Publication number

Priority date

Publication date

Assignee

Title

US20210406752A1

( en )

2017-06-19

2021-12-30

Rigetti & Co, Inc.

Distributed Quantum Computing System

US11727299B2

( en )

2017-06-19

2023-08-15

Rigetti & Co, Llc

Distributed quantum computing system

US20230419141A1

( en )

2017-06-19

2023-12-28

Rigetti & Co, Llc

Distributed Quantum Computing System

US12020118B2

( en )

2017-06-19

2024-06-25

Rigetti & Co, Llc

Distributed quantum computing system

US20240338213A1

( en )

2021-04-21

2024-10-10

Origin Quantum Computing Technology (Hefei) Co., Ltd

Quantum computing platform adaptation method and apparatus, and quantum computer operating system

US12498922B2

( en )

2021-04-21

2025-12-16

Origin Quantum Computing Technology (Hefei) Co., Ltd

Quantum computing platform adaptation method and apparatus, and quantum computer operating system

RU2826431C1

( en )

2024-03-19

2024-09-10

Method and system for distributing computational tasks in cloud environment

Also Published As

Publication number

Publication date

US20180307988A1

( en )

2018-10-25

EP3392808B1

( en )

2023-09-27

EP3392808A1

( en )

2018-10-24

Solving computational tasks using quantum computing — Accenture Global Solutions Limited (US11250334B2)

Related documents