Feeds as Query Result Serializations

Many Web-based data sources and services are available as feeds, a model that provides consumers with a loosely coupled way of interacting with providers. The current feed model is limited in its capabilities, however. Though it is simple to implement and scales well, it cannot be transferred to a wider range of application scenarios. This paper conceptualizes feeds as a way to serialize query results, describes the current hardcoded query semantics of such a perspective, and surveys the ways in which extensions of this hardcoded model have been proposed or implemented. Our generalized view of feeds as query result serializations has implications for the applicability of feeds as a generic Web service for any collection that is providing access to individual information items. As one interesting and compelling class of applications, we describe a simple way in which a query-based approach to feeds can be used to support location-based services.

Introduction
Feeds have become the most popular format for machine-readable data on the Web; they can be considered to be the most successful "Web service" available today. Feeds can be based on various data formats, either a considerable number of variations of the RSS format, or the more well-defined Atom [11] format. For the purpose of this paper, we do not look at the specifics of a particular feed format, but we do assume that feeds are using a well-defined format, and we will use Atom's terminology of a feed for the aggregate data structure, and of an entry as one item in that aggregate data structure. Based on the terminology of the Atom Publishing Protocol (AtomPub) [7], we use the term collection to refer to the data source underlying the feed, and a collection is a set of members. All of this means that a feed can be regarded as a standardized way to publish a set of members of a collection in the form of feed entries. Figure 1 is an illustration of this relationship between feeds, entries, collections, and members, which can be regarded as an example of the typical Web architectural pattern of resources (collections and members) and representations (feeds and entries).
In this paper, we investigate the applicability of feeds as a general format for query result serializations. We specifically address the missing parts of the current landscape of feed-related standards, and the question of how well feeds work as a general format for query result serializations. This investigation is a part of a more general question of how far the general concept of feeds can be taken, and Section 4 goes into more details about some of the scenarios in which feeds as a general format for query result serializations are a compelling design approach for for establishing a loosely coupled landscape of information and service providers. Generally speaking, we focus on feeds because in a view of Web engineering that is more centered on the Web than it is on back-end engineering [19], feeds stand out on today's Web as the most popular Web service in use. Feeds (in particular when AtomPub is taken into account as well) are a good example for how to use Representational State Transfer (REST) [6] as a design principle, and thus using feeds can be a promising approach when RESTful design is required.

Current Status
The current status of feed technologies on the Web can be regarded in terms of standards and standardization proposals (Section 2.1), and implementations (Section 2.2). Standards often lay the foundation and may explore interesting areas for generalized solutions, whereas implementations often are driven by the specific needs of an application or service provider. From the application area point of view, feed technologies started with RSS and then progressed to Atom when the RSS standardization situation became unsatisfactory for information providers interested in a stable, well-defined, extensible, and predictably evolving standard for feeds. The main application area for feeds from the end-user point of view are blogs and similar providers of time-ordered information streams (such as news agencies). Increasingly, feeds are used for any time-ordered stream of other types of content, for example photo management services such as flickr, Picasa, or Panoramio provide photo streams as feeds, allowing users to keep track of these streams with any service or tool supporting feeds.
In some of these scenarios, services are using their own conventions or extensions of feed technologies, but for all of these scenarios, the feed-related standards described in Section 2.1 are readily available.

Standards
The earliest instances of feed technologies were various RSS versions. RSS was riddled with a number of problems, caused by poor specifications (leaving crucial details to implementations), shifts in the basic syntax (some RSS versions are based on XML, others are based on RDF), disagreements in the community about the future path of the specification, and no clear stewardship for the specification itself. 1 As a way out of this situation, Atom [11] (first named Echo) was created under the auspices of the IETF, and the main goals were a well-defined standard with unambiguous interpretation of the standard itself, and clear extension rules for how to extend the standard's basic model. In addition to the basic Atom model, there are standardized extensions for how to encode threaded discussions using Atom Threading Extension [16], how to embed licensing information in Atom feeds using the Atom License Extension [17], and how to publish various feed types for Feed Paging and Archiving [9]. These extensions cover scenarios that are recurring patterns for applications providing feeds, and allow standardized interactions around these recurring patterns.
Even though initially defined for RSS, GeoRSS [13] can also be used for Atom and is an extension for including geolocation information in feeds; the underlying geolocation model is the Geography Markup Language (GML) [12]. GeoRSS has two profiles, GeoRSS Simple and GeoRSS GML, with the former supporting point, line, polygon and box geometries, whereas the latter supports a wider array of features (such as alternative coordinate systems) and is formally defined as a profile of GML. Essentially, GeoRSS simply adds location information to the feed data model, but as we will see in Section 4, location as part of the data model is important in a wide variety of use cases for interacting with feeds.
The Atom Publishing Protocol (AtomPub) [7] is an extension of Atom which allows HTTP-based interactions with a provider of Atom feeds. While feeds are a read-only format, AtomPub extends the Atom feed model to cover all REST verbs, so that users can interact with an AtomPub-enabled collection by creating, updating, and deleting entries. While AtomPub is a useful extension of Atom's read-only model, in this paper we only consider queries and thus read-only accesses to Atom-enabled collections.

Implementations
For basic feed providers, Atom provides a sufficient foundation for publishing information, but as soon as information providers want to publish more sophisticated feeds for more specific access to the underlying collection, it gets more complicated. For example, one of the parts of Atom's data model are categories, and entries can be labeled with any number of categories. If information providers want to publish categoryspecific feeds, they can do so at different URIs, but then it is no longer clear that these feeds essentially are just different "views" of the same underlying feed or collection. Some blog services, for example, provide users with the ability to publish category-specific feeds, and blog posts are published in the feeds for the categories that were used to tag them, as well as in the general feed.
This situation becomes even more difficult when users should be allowed to subscribe to feeds with more than one category assigned to it; in this case, the feed provider has to invent some convention for expressing the categories contained in the feed. 2 The technology Q&A site stackoverflow.com, for example, has introduced a custom syntax for this, allowing feed URIs to carry query information and supporting and, or, and not operators, using a simple syntax: 3 • java and jsp: http://stackoverflow.com/feeds/tag/java jsp • java and not jsp: http://stackoverflow.com/feeds/tag/java -jsp • java or jsp: http://stackoverflow.com/feeds/tag/java or jsp While this provides useful functionality, this solution has two drawbacks: it may compromise a service's scalability (more on this topic in Section 3.1), and it is specific for this one service, so that clients cannot easily support this feature programmatically across different providers.
Google's GData protocol combines Atom and AtomPub, and also covers query features for feeds. It is intended as a general API for accessing many of the data sources and services provided by Google. GData uses a different syntax than the one presented above, but very similar functionality. The GData syntax for the above feed URIs would look like this: • java and jsp: http://stackoverflow.com/feeds/-/java/jsp • java and not jsp: http://stackoverflow.com/feeds/-/java/-jsp • java or jsp: http://stackoverflow.com/feeds/-/java|jsp In addition to categories, GData supports full-text queries, author searches, range queries on the updated and published timestamps, and methods for specifying the results as number of entries, the start index of the returned results, and the returned data format. The GData query model is more a filter than it is a full query: all query predicates are scoped to a single entry, and thus the complete query acts as a filter for each entry individually. One apparent limitation of GData is that it allows queries on nothing else but the data exposed in a feed (more on that distinction in Section 5, which discusses the difference between querying feeds and querying collections).
An alternative approach is the Feed Item Query Language (FIQL) [10], which also specifies a query syntax for feeds, but defines a more general set of operators, datatypes, and values which can be used for queries. Most importantly, FIQL defines a way how a feed provider can advertise its query capabilities in the feed itself using a query interface, which means that a feed can advertise the query capabilities of the underlying collection. While FIQL is an interesting approach and heads in an interesting direction, the initial and expired draft was never updated, and no known implementations exist.
Two other implementations supporting query-oriented interactions with feeds are Yahoo Pipes and the Yahoo Query Language (YQL). Pipes is a visually oriented tool for how users can connect various feedprocessing modules, and can aggregate and filter feed data (or other data providers which are turned into feeds) to generate one result feed. The fundamental limitation of Pipes is that it only works on the feed level, not on the collections, because the platform is designed as an intermediary between feed providers, and the consumer of the feed generated by the platform. YQL also supports various data input (including feeds), but the output is YQL-specific XML or JSON. So while YQL targets the same goal as GData, a uniform access to various data sources provided by the respective companies, it is not using feeds as its fundamental data model. Even though it is not strictly feed-based, OpenSearch is another widely recognized approach to consider. It was developed by A9, a subsidiary of Amazon, and mostly is a standardized API for search engines. The interesting fact is that OpenSearch uses feeds with extensions as the result format. As the query format, OpenSearch defines XML formats (one for describing the interface, and one for the query itself), as well as URI templates. The main conceptual limitation of OpenSearch is that it is focused on full-text search.

Implementation Issues
One of the most important reasons for the success of feeds is that they are an excellent example of loose coupling [14]. They provide a resource-oriented and easily usable way of accessing a great variety of service providers, and allow both providers and consumers to use simple implementations. Even though colloquially speaking people often talk about "subscribing to a feed", there actually is no such thing as a feed subscription; servers provide feeds, and clients read feeds. This approach provides looser coupling than publish/subscribe approaches [5] (which forces publishers to keep track of all subscribers and deal with stale subscriptions), and allows servers and clients to benefit from standard Web mechanisms for load balancing, such as HTTP intermediaries (which might or might not act as caches).

Server-Side
The most important benefit from the server-side point of view is the almost perfect scalability of feeds. Since feeds are often provided as static Web resources, servers can refresh these resources as required, and they can be served as static documents in between updates. This is possible because all clients get the same feed when they request it; there is no such thing as a client-specific feed. This "one size fits all" approach allows servers to scale to millions of feed consumers with little effort, because feed requests by clients do not cause any back-end query. Feed providers can use standard Web methods and appliances to improve performance, should scalability become an issue.
Purely category-specific feeds (one feed per category) could be regarded as a "few sizes fit even more" approach, which could still be easily implemented with static feeds, which are only refreshed when new entries are published. As long as individual client requests are not mapped to individual back-end queries, feeds scale well. On the other end of the extreme are individual feed queries, which are the equivalent of the observation that "personalized sizes are expensive to provide", at least as long as the personalization process is not optimized. If individual feed queries are naïvely mapped to back-end queries, scalability suffers (Section 5.1 goes into more detail about this question).
However, even with naïve implementations it is possible to imagine scalable scenarios, where free access to feed-based data sources is provided with the current non-queryable feed model; and as a value-added service it is also possible to get query access to the feed for more advanced applications. However, this query-enabled access would be controlled through mechanisms such as HTTP authentication or API keys for enforcing access limits and/or paid subscriptions; thereby giving the feed provider the ability to better control feed access through a two-tier access scheme (read-only access and query access).

Client-Side
While the main advantage of the simplicity of the current feed model lies with servers and their ability to scale easily, clients also gain some benefits from feed processing. While there is no guarantee that the entries in feed are ordered by time (which would allow clients to do more optimized processing), Atom does guarantee that feed entries have unique and stable identifiers. By keeping track of these identifiers, clients can synchronize the entries in a feed they read with previously read entries, and update their local storage.
If a feed supports Feed Paging and Archiving [9], clients can interact with a feed in a manner guaranteeing that they will not loose any entries. This Atom extension supports archived feeds, which essentially are stable feeds which are supposed to contain all the entries of a logical feed. Typically, clients reread feeds as required, and they do not necessarily care about the fact whether they have missed some entries because the feed was updated faster than they were rereading it. However, if a feed supports archiving, clients interested in the complete history of a feed can always retrieve the complete history of a feed by following links to archived feeds.
Client-side processing and optimizations often look at the current model of feeds, which is based on the implicit assumption that updates will appear in feed, and that by rereading a feed at an appropriate interval, clients can get a complete picture of the updated entries for the underlying collection. In Section 4, we look at scenarios where the collection itself, or the interactions with a collection, do not map well to this model of feeds, and where an explicit query mechanism for feeds would significantly improve the applicability of feeds.
It should be kept in mind, though, that Feed Paging and Archiving already is a first step in that direction: the ability to have paged and archived feeds already establishes a richer set of interactions between feed providers and consumers, even though in this case this is not implemented in a query language, but by using special link relationships. It should be noted that many feed providers supporting feed paging already do so by linking these link relationships to "pseudo-query" URIs such as "...feed.xml?page=2" when linking to the second page of a paged feed.

Feed Query Scenarios
The previous sections have pointed out how feeds today are mostly used in a "one size fits all" approach, and how this pattern so far has been only partly broken by proprietary implementations such as GData and YQL, or by specialized extensions such as Feed Paging and Archiving. The current main scenario is based on feed access regardless of the specific needs of the feed consumer. Location-Based Services (LBS) [15] are a popular example where access to an information source or service is location-dependent. In this case, the location of a feed consumer should result in different responses of the service provider, depending on the resource.
As one example, it is possible to envision a general feed reader (similar to, for example, the popular Google Reader) aggregating several feeds, but these feeds are location-enabled and support location-based access. Such a "geofeed reader" would probably use a map-based interface or at least some map view of the retrieved information. 4 In such an interface, the map view could be regarded as an "implicit query", so that user interactions with the map view would cause the feeds to be queried for the new view. Such an interface would be particularly interesting for mobile devices, which in many cases are used in LBS scenarios, and which also can benefit from the significant bandwidth optimization of only requesting those entries which are relevant to the current location or map view.
While the LBS scenario in combination with query-enabled geofeeds alone is a rather compelling use case, more complex models of user interests and situations than just the location [8] can also be employed. Mapping such a more complex situational model to feeds and feed queries (if they have various query capabilities) becomes a flexible and powerful way of service personalization. Feeds could be pulled from a large variety of providers, more traditional feed publishers such as news agencies, but also information from sources such as traffic sensors (when the situation is recognized as requiring traffic information). Generally, in such a scenario the situational context can be seen as a query into an aggregated set of feeds, and the expected response is the aggregated set of results from all of these services, providing the most useful information for the current situation. The hard challenges in this scenario are figuring out how to know which feeds to aggregate, and how to map the situational context to the query capabilities of those feeds; once these challenges have been met, using feeds as the serialization format establishes a common and loosely coupled foundation for the feed providers and consumers to cooperate.
Feeds are often regarded as a serialization of inherently time-ordered data, but there is nothing in the Atom specification that prevents a feed from being used as a way to serialize data that has other primary keys than a timestamp (the only thing required by the specification is that each entry must have an updated timestamp, indicating when an entry was last updated). In addition, the specification assigns no significance to the order of entries within a feed. Consequently, a service responding to a feed query with a result feed can choose to sort the results in any way, and most importantly, if the query language also supported features such as sort-by and group-by constructs, the results could be ordered according to these parameters.

Query Models
Based on the scenarios presented in the previous section, this section looks at considerations for the specific query data model and language. Sections 5.1 to 5.3 look at the question of the extent of such a query language, i.e. at the question of what should be queryable. Sections 5.4 and 5.5 then look at the issue of the query language itself and how it could support queries joining entries from one feed, or even across aggregated feeds.
Some of the implementations discussed in Section 2.2 have query data models that are specific for specific data sources. GData and YQL have been designed as unified interfaces for various services provided by the respective companies, and thus have well-defined ways of how information specific to these services can be retrieved using these languages. However, this means that these services are essentially hard-coded into the languages' specifications, defining how specific services can be used with these languages. While this makes sense as an approach for integrating a rather small and centrally controlled set of services, it is not an approach that readily translates into an open scenario.
Furthermore, none of the implementation described in Section 2.2 cover geolocation as part of their data model, and we believe that geolocation is a concept important enough that it should be part of the standard interactions with a feed-based collection. Sections 5.1 and 5.2 explore the basic difference between interactions only using data contained in the feed, or interactions which also can use additional data contained in the collection.
The question of the best data model and query language for feeds has quite a bit of similarity to the problem of federated databases, but there are some relevant differences. One point is that it can be assumed that the collections underlying feeds are using very different data models, and these data models are also based on different metamodels. On the other hand, since these collections are published as feeds, there is some mapping from their data models to the feed data model. This means that on the one hand the feed data model is useful because it provides a universal metamodel across feeds, but this also means that for many collections, only parts of the collection's model will be mapped to feeds, while other are "invisible" on the feed level. 5 This unified view of collections introduces an interesting opportunity for large-scale information mining. Individual collections can expose services which are specifically designed for these collections, and cannot be used outside of their scope. On the other hand, feeds can be aggregated and then they become "view" of these individual collections, represented in a unified way. This aggregated information can then be used to perform cross-collection queries which would have been impossible when dealing only with individual collections. Section 5.5 goes into more details about the query features required for this scenario, but it is worth pointing out that the two levels of collections and feeds, of implementation-specific and standardized data formats, enable new forms of data filtering and aggregation that would be impossible with a less loosely coupled approach.

Feed Queries
The most limited data model for feed queries is one that only takes the standardized fields of feeds into account. According to the Atom specification, a feed can have 12 possible element types as children that will describe the feed itself, and each entry in a feed can also have 11 possible element types (almost the same ones as the feed) as children that will describe the entry. The entry element either contains or links to the actual content, which can be text, HTML, XHTML, or some MIME media type. In Atom's metadata elements, various data types are used, most notably text, timestamps, URIs (Atom actually uses IRIs), and email addresses.
The elements and datatypes defined by Atom itself are the most restricted subset that could be considered for querying feeds (if we do not consider pure full-text search approaches such as OpenSearch). Based on the datatypes, query operators for these elements could include complete and partial matches for text, URIs, and emails, and range queries for timestamps. For text, more advanced query methods could be full-text search methods such as thesaurus-based search, stemming, case-control, and support for diacritics.
Such a query language operating on the feed data alone could be implemented by mapping it to XQuery [2] (possibly extended by XQuery's full text extension [1], if full-text search is considered as well). Depending on the underlying collection, though, for the feed provider it would be the more efficient option to map a feed query to the query language of the back-end, so that the query could be optimized as much as possible.
One important issue to point out is that the query model presented here, as well as the one presented in the following section, is only operating on the feed level. This means that an intermediary with no knowledge of the back-end of the feed provider is able to execute the same queries; limited of course to those entries that have been cached by that intermediary. While those intermediaries can be any HTTPlevel intermediaries, there are also scenarios where a feed provider specifically decides to publish their feed through an intermediary, usually for load balancing and/or analytics. One such example is FeedBurner, a company that is now part of Google. They act as intermediaries for feed providers, and cache feeds (though not necessarily the complete history of a feed) and thereby greatly reduce the load for feed providers. If such a intermediary does archive feed entries, however, it can also process feed queries based on this archive.

Extended Feed Queries
While Atom itself uses the rather small set of element types mentioned in the previous section, it also has a well-defined extension model, and extension elements can appear within feeds as well as within entries. One such extension is GeoRSS markup, which encodes geospatial information in a feed. In a strictly feed-based model as the one described in Section 5.1, this information cannot be queried, because it is not part of Atom itself. However, there are useful extensions to Atom specifying additional elements for feeds and entries, GeoRSS is one of them, the Atom License Extension [17] is another one.
In both of these examples, the extensions specify a way in which additional information can be embedded in a feed, essentially extending the information that may appear in the feed, as well as the data model. In case of GeoRSS, this is especially important because it adds the complexity of the GML model to feeds, whereas licensing information is made available through a new link relation type, and thus is reduced to a URI/IRI in terms of its contributions to the information in the feed itself.
These examples thus show the breadth of problems that may occur when considering the ability to add query capabilities for feed extensions. For license information, this essentially means to query for standard link elements, but only those using a standardized relationship. Thus, if the query language supports queries on links that take into account the relationship, the relationship's namespace, and the link's target, querying for specifically licensed entries can be done.
On the other hand, for GeoRSS, the feed extension introduces new elements and new data types, and for querying to be able to work on this as well, the query method must be more radically extended.
Since we assume that query capabilities will always be based on the collection being published in a feed, it would make sense to define extended query capabilities as separate modules, so that an extension such as GeoRSS would have an accompanying specification defining the query capabilities for this extension. For this to work, the query language must have a well-defined and modular extension system. While GeoRSS is used by a large set of feed providers, such a model would also allow service-specific extensions to fit into the framework of the query language, so that service providers such as Google and Yahoo could define and publish their own modules. Reusable modules would be the preferred way, though, because then feed consumers can interact with any service providing feeds and query capabilities with that functionality.
One interesting approach taken by FIQL is to allow feed queries to use XML Path Language (XPath) [4] expressions to identify values that can used in queries. While this makes it possible to select markup constructs such as feed extensions, and thus introduces some extensibility into the query language, in case of GeoRSS this would be of little use, because selecting GeoRSS elements will return GML, and thus this datatype (which allows rather complex geometric shapes to be used) must be known to be able to process these values.
More generally speaking, while it is possible to create an extensible feed query language that does support basic feed elements and datatypes as described in Section 5.2, and can be extended in a modular way, there still is no way how feed providers can expose services beyond the information contained in the feed. This is good from the standpoint of intermediaries, because this means that whatever feed consumers can get from a feed provider, they can also get from an intermediary; but it ignores the fact that the collection itself may have more capabilities than those represented in its feed serialization.

Collection Queries
The feed queries described in the previous sections are limited to the data that is available in a feed, they cover standard elements of Atom (Section 5.1) and extensions (Section 5.2). The next logical step is to expose the query capabilities of the collection, which may go beyond what is represented in the feed.
As an example, a collection of images could be exposed through a queryable feed, and users of that collection could query for images using standard Atom fields (such as a title or a timestamp), or they could query for images using information that is available in the feed as extensions (such as the location where a picture was taken, or the license under which it has been published). However, more advanced services such as content-oriented image search could also be provided, giving users the opportunity to search for images by textual descriptions of what they are looking for, or maybe by providing example images.
This query capability of the service is not at all exposed in the feed itself, but it may be an important service provided by the collection. Thus, including query capabilities which not only extend Atom's data model and datatypes, but also have no representation in the feed itself once the query has been processed, could greatly expand the possible application areas of feed-based querying.
It should be kept in mind, though, that such a collection-based query is something that cannot be supported by intermediaries, because these have only access to the feed data, but not to the collection. Thus, if a service provider is interested in supporting intermediaries on the feed level (for example for load balancing), then collection queries cannot be used. If collection queries are used, queries must be run on the collection in the back-end, and possible load balancing then has to be done on that level as well.

Cross-Entry Queries
The query models described in the previous sections are of increasing complexity regarding the ability to query data beyond the feed data model itself, but they do not necessarily extend the query model beyond simple filtering capabilities. The next possible level of complexity is that of queries relating entries to each others; in relational databases, this operation is often referred to as a join, and since a feed is just one data structure, more specifically it could be regarded as a self-join.
Since collections accessible through feeds often do have timestamps associated with them, a special case of self-join would be temporal queries, which often are queries such as "find all entries where there were more than three entries published over the course of one hour". Another interesting special case of self-joins are spatial queries, which essentially can exhibit the same nature than temporal queries, but extend time's one-dimensional model to the 2D or 3D space of the underlying spatial model. Spatial queries often require the same self-join logic as temporal queries, asking questions like "find all entries in places where there are more than a certain number of entries in a given area".
Combining temporal and spatial queries leads to the field of spatio-temporal databases, which is a wide and well-established field of research and productive systems. More specifically, sensor networks add an additional complication to this field by often using models of streaming data, so that spatio-temporal queries must be processed in real-time and over potentially a large number of incoming datastreams. Sensor networks typically have a large volume of incoming data (the "collection", which in this case is a continually updated set of datastreams), and ideally should only produce a small volume of outgoing data (the feed of relevant events). In such a network, queries often are used for alerting systems, so that for example a sustained condition over a certain period of time can trigger an alert.

Cross-Feed Queries
Using feed query capabilities for querying a given sensor network alone already can provide substantial benefits by providing a uniform interface for different underlying implementations of sensor networks [18]. However, more interestingly, if the results produced by different sensor networks can be easily aggregated and processed, even more opportunities for using sensor networks become visible.
As mentioned in Section 5, one very important use case for cross-entry queries are aggregated feeds. If feeds are regarded as query result serializations of individual services, these results can be aggregated and then queried again. This kind of query can be regarded as a join across multiple feeds, allowing it for example to use the aggregation of two geofeeds, and query this aggregation for spatial co-occurrences of entries across the feeds, thereby joining the feeds in a spatial manner.
This last scenario for cross-entry queries would make it necessary to augment a feed with the origin for each individual entry, so that aggregated feeds still contain the information in which feed an individual entry originally occurred. We call such an aggregated feed a feedset, and while a feedset is just a feed, the interesting fact about is that its entries correspond to members from more than one collection, turning it into a representation of resources across various collections. Figure 2 shows an example of a feedset, and it is important to note that the various collections represented by a feedset are not necessarily related by anything more than the fact that both of them are accessible through feeds. 6 When considering cross-entry queries as discussed in Section 5.4, and cross-feed queries as a even more powerful concept for feed queries, it is important to consider the implementation options for such a language. Considering feed providers, intermediaries, and feed consumers in such a scenario, the following observations can be made: • Pure filtering capabilities as well as cross-entry queries can be performed by the feed provider. They could also be performed by intermediaries (as long as queries are not collection-based, in which case only the feed provider can process them), but in terms of optimization, pushing them as far upstream as possible is preferable.
• Cross-feed queries, on the other hand, cannot be performed by feed providers, because the very nature of these queries requires an aggregation of feeds before the queries can be performed. This means that the model of intermediaries is a very useful one for these queries, because queries can then be pushed as far upstream as possible (i.e., to the intermediary performing the aggregation).
This means that for query optimization and when looking at a scenario where a feed consumer is aggregating various feeds, query processing should be able to be done in a distributed fashion, so that filtering of feed entries can be done as far upstream as possible, reducing the bandwidth and processing load required further downstream.

Discovery
It is also important to consider how a feed's query features can be discovered. For today's feeds, no discovery is required, because a feed is not query-enabled. However, Feed Paging and Archiving (as described in Section 3.2) already does introduces minimal "query features" for a feed, and does so by adding special links to a feed. This means that discovery of that feature is entirely feed-based; a client can simply retrieve a feed and will understand whether that feeds support paging and/or archiving or not.
The same principle should be used for the more complex query features discussed in Section 5. FIQL and OpenSearch both define ways in which a client can discover the query features of a service provider. The mobile map-based geofeed client described in Section 4 should be able to retrieve a feed, figure out the feed's query capabilities, and query that feed according to the feed's capabilities. The query can be driven by the current map view, some internal situational model, or an explicit user interface that is generated based on the feed's query capabilities. The important benefit of this design is that no prior configuration is required, and providers and consumers can interact spontaneously.

Conclusions
Feeds are the most prolific Web service available on the Web today. Based on a simple and loosely coupled model, they allow feed consumers to interact with a variety of service providers. By looking at the current feed model as a simple version of how feed consumers get representations of queries run on the feed provider side, it is possible to envision extensions of that simple model. Based on the current standardization and implementation landscape, and taking implementation issues for both providers and consumers into account, an extension of the current model of "hardcoded" queries to a more flexible and powerful model can be envisioned.
Generally speaking, the view of feeds as query result serializations, and a possible extension of the feed format to provide query support, is an attempt to allow declarative ways of how feed consumers and providers can interact. The detailed implementation issues for query-enabled feed services are outside the scope of this paper, but many research results from focused research areas such as federated databases, distributed query processing, sensor networks, and spatio-temporal databases could be leveraged to address many of the challenging research questions.
It should be noted that while in this paper we have not looked at issues of authentication, access control, and security, many of the standard issues in this areas could be readily addressed by using standard Web technologies.


extfieldsofstudy:
Computer Science
Physics

text:
Hoare Logic for Quantum Programs

Hoare logic is a foundation of axiomatic semantics of classical programs and it provides effective proof techniques for reasoning about correctness of classical programs. To offer similar techniques for quantum program verification and to build a logical foundation of programming methodology for quantum computers, we develop a full-fledged Hoare logic for both partial and total correctness of quantum programs. It is proved that this logic is (relatively) complete by exploiting the power of weakest preconditions and weakest liberal preconditions for quantum programs.

Introduction
Even though quantum hardware is still in its infancy, people widely believe that building a large-scale and functional quantum computer is merely a matter of time and concentrated effort. The history of classical computing arouses that once quantum computers come into being, quantum programming languages and quantum software development techniques will play a key role in exploiting the power of quantum computers. With expectation of offering effective programming techniques for quantum computers, several quantum programming languages have already been designed in recent years. The earliest proposal for quantum programming language was made by Knill [13]. The first real quantum programming language, QCL, was proposed byÖmer [16]; he also implemented a simulator for this language. A quantum programming language in the style of Dijkstra's guarded-command language, qGCL, was presented by Sanders and Zuliani [18]. A quantum extension of C++ was proposed by Bettelli et al [6], and it was implemented in the form of a C++ library. The first and very influential quantum language of the functional programming paradigm, QFC, was defined by Selinger [19] based on the idea of classical control and quantum data. In [2], Altenkirch and Grattage defined another functional programming language for quantum computing, QML, in which both control and data may be quantum. For excellent survey of quantum programming languages, see [20,12].
The fact that human intuition is much better adapted to the classical world than the quantum world is one of the major reasons that it is difficult to find efficient quantum algorithms. It also implies that programmers will commit much more faults in designing programs for quantum computers than programming classical computers. Thus, it is even more critical than in classical computing to give clear and formal semantics to quantum programming languages and to provide formal methods for reasoning about quantum programs. Indeed, various semantic approaches to quantum programs have been proposed in recent literatures. For example, an operational semantics was given to Sanders and Zuliani's language qGCL [18] by treating an observation (quantum measurement) procedure as a probabilistic choice; a denotational semantics was defined for Selinger's language QPL [19] by interpreting quantum programs as super-operators; and a denotational semantics of Altenkirch and Grattage's language QML [2] was described in category-theoretic terms. In addition, a language-independent approach to semantics of quantum programs was proposed by D'Hondt and Panangaden [10] who introduced an intrinsic notion of quantum weakest precondition and established a beautiful Stone-type duality between state transition semantics and predicate transformer semantics for quantum programs.
As to proof systems for reasoning about quantum programs, Baltag and Smets [4,5,1] presented a dynamic logic formalism of information flows in quantum systems, which is capable of describing various quantum operations such as unitary evolutions and quantum measurements, and particularly entanglements in multi-partite quantum systems. Brunet and Jorrand [8] introduced a way of applying Birkhoff and von Neumann's quantum logic [7] to the study of quantum programs by expanding the usual propositional languages with new primitives representing unitary transformations and quantum measurements. In [9], Chadha, Mateus and Sernadas proposed a Hoare-style proof system for reasoning about imperative quantum programs using a quantitative state logic, but only bounded iterations are allowed in their programming language. Feng et al [11] found some useful proof rules for reasoning about quantum loops, generalizing some of Morgan's proof rules for probabilistic loops [14]. To the author's best knowledge, however, no complete Hoare logic for quantum programs has been reported in the literature.
The main contribution of the present paper is the establishment of a full-fledged Hoare logic for deterministic quantum programs based on Selinger's idea of modeling quantum programs as super-operators and D'Hondt and Panangaden's notion of quantum predicate as an Hermitian operator [10]. This logic includes a proof system for partial correctness and a proof system for total correctness of deterministic quantum programs. In particular, we are able to prove its (relative) completeness by exploiting the power of weakest preconditions and weakest liberal preconditions for quantum programs. The paper is organized as follows: For convenience of the reader, we recall some basic concepts of Hilbert spaces as well as the fundamental postulates of quantum mechanics in Section 2. Another aim of Section 2 is to fix notation used in the sequel sections. In Section 3, we define the syntax of deterministic quantum programs about which the Hoare logic presented in this paper is designed to reason. Such quantum programs are quantum extension of classical while-programs (cf. [3], Chapter 3). In Section 4, an operational semantics of quantum programs is given in terms of transitions between quantum configurations, which consist of a quantum program still to be executed and a (partial) density operator expressing the current state of program variables. In Section 5, we are able to introduce a denotational semantics of quantum programs based on the operational semantics. A denotational semantics of a quantum program is defined to be a function from partial density operators to themselves. In Section 6, we adopt D'Hondt and Panangaden's definition of quantum predicates as Hermitian operators. Then a correctness formula is defined to be a quantum extension of Hoare triple, which consists of two quantum predicates, namely precondition and postcondition, as well as a quantum program. Furthermore, the notions of partial and total correctness can be introduced for quantum programs using their denotational semantics. In Section 7, weakest precondition and weakest liberal precondition for quantum programs are defined in terms of total and partial correctness, respectively, in a familiar way. With the long preparation of the previous sections, the Hoare logic for quantum programs is finally established in Sections 8 and 9. In Section 8, a proof system for partial correctness of quantum programs is presented, and its (relative) completeness is proved, and in Section 9, after introducing the notion of bound function for quantum loops, a proof system for total correctness of quantum programs is given, and its (relative) completeness is also proved. A brief conclusion is drawn and some open problems for further studies are pointed out in Section 10.
For any vector |ψ in H, its length ||ψ|| is defined to be ψ|ψ . A vector |ψ is called a unit vector if ||ψ|| = 1. Let {|ψ n } be a sequence of vectors in H and |ψ ∈ H. If for any ǫ > 0, there exists a positive integer N such that ||ψ m − ψ n || < ǫ for all m, n ≥ N , then {|ψ n } is called a Cauchy sequence. If for any ǫ > 0, there exists a positive integer N such that ||ψ n − ψ|| < ǫ for all n ≥ N , then |ψ is called a limit of {|ψ n } and we write |ψ = lim n→∞ |ψ n .
A family {|ψ i } i∈I of vectors in H is said to be summable with the sum |ψ and we write |ψ = i∈I |ψ i if for any ǫ > 0 there is a finite subset J of I such that ||ψ − i∈K ψ i || < ǫ for every finite subset K of I containing J. A family {|ψ i } i∈I of unit vectors is called an orthonormal basis of H if 1. |ψ i ⊥ |ψ j for any i, j ∈ I with i = j; and 2. |ψ = i∈I ψ i |ψ |ψ i for each |ψ ∈ H.
In this case, the cardinality of I is called the dimension of H.
A Hilbert space is defined to be a complete inner product space; that is, an inner product space in which each Cauchy sequence of vectors has a limit. According to a basic postulate of quantum mechanics, the state space of an isolated quantum system is represented by a Hilbert space, and a pure state of the system is described by a unit vector in its state space.
The inner product in H 2 is defined by An operator A on H is said to be bounded if there is a constant C ≥ 0 such that A|ψ ≤ C · ψ for all |ψ ∈ H. In this paper, we only consider bounded operators. We write L(H) for the set of bounded operators on H. A density operator ρ on a Hilbert space H is defined to be a positive operator with tr(ρ) = 1. Then a mixed state of a quantum system with state space H is described by a density operator on H. In this paper, we take a slightly generalized notion of density operator in the sequel: a partial density operator ρ is a positive with tr(ρ) ≤ 1. In particular, the zero operator is a partial density operator. The set of partial density operators is denoted D − (H). A partial density operator can also be defined by an ensemble of pure states. Suppose that a quantum system is in one of a number of pure states |ψ i , with respective probabilities p i , where it is required that i p i ≤ 1. Then is a density operator. Conversely, any density operator can be generated in such a way.

Unitary Transformations
and the Pauli matrices: 2. Let k be an integer. Then the k−translation operator on H ∞ is defined by It is easy to verify that U +k is a unitary operator.
The basic postulate of quantum mechanics about evolution of systems may be stated as follows: Suppose that the states of a closed quantum system at times t 0 and t are |ψ 0 and |ψ , respectively. Then they are related to each other by a unitary operator U which depends only on the times t 0 and t, This postulate can be reformulated in the language of density operators as follows: The state ρ of a closed quantum system at time t is related to its state ρ 0 at time t 0 by a unitary operator U which depends only on the times t and t 0 ,

Quantum Measurements
A quantum measurement on a system with state space H is described by a collection where M m are called measurement operators, and the index m stands for the measurement outcomes that may occur in the experiment. If the state of a quantum system is |ψ immediately before the measurement, then the probability that result m occurs is p(m) = ψ|M † m M m |ψ and the state of the system after the measurement is We can also formulate the quantum measurement postulate in the language of density operators. If the state of a quantum system was ρ immediately before measurement {M m } is performed on it, then the probability that result m occur is and the state of the system after the measurement is A special class of quantum measurements will be frequently used in the sequel: If a measurement M has only two outcomes, say 0 and 1; that is, M = {M 0 , M 1 }, then we often call M a yes-no measurement, with 0 corresponding to "no"and 1 to "yes".

Tensor Products of Hilbert Spaces
The state space of a composite quantum system is the tensor product of the state spaces of its components. In this subsection, we recall the definition of the tensor product of a family {H i } of Hilbert spaces. For simplicity of presentation, it will be assumed that the set of quantum variables is countably infinite, and the type of each quantum variable is either Boolean or integer (see next section). Thus, we only need to consider a finite or countably infinite family {H i } where each H i is finite-dimensional or countably infinite-dimensional. A more general notion of tensor product introduced by von Neumann [21] should be adopted in order to generalize the results obtained in this paper to the case of more quantum variables and other types.
Let {|ψ ij i } be an orthonormal basis of H i for each i. We write B for the set of tensor products of basis vectors of all H i ; that is, Then B is a countably infinite set, and it can be written in the form of a sequence of vectors: B = {|ϕ n : n = 0, 1, ...}.
The tensor product of {H i } is defined to be the Hilbert space spanned by B, i.e.
We define the inner product in i H i as follows: ( n α n |ψ n , n α ′ n |ψ n ) = n α * n α ′ n for any α n , α ′ n ∈ C, n ≥ 0. It is easy to see that i H i is isomorphic to H ∞ . The notion of partial trace is very useful for description of a subsystem of a composite quantum system. Let H and K be two Hilbert spaces and operator A ∈ L(H ⊗ K). Then the partial trace of A on H is defined to be which is an operator on H, where {|ψ i } is an orthonormal basis of K. It can be shown that tr K (A) does not depend on choice of {|ψ i }. In particular, if H 1 and H 2 are the state spaces of quantum systems q 1 and q 2 , respectively, and the state of their composite system q 1 q 2 is described by a density operator ρ ∈ D − (H 1 ⊗ H 2 ), then tr H 2 (ρ) is the description for the state of component system q 1 .

Syntax of Quantum Programs
We assume a countably infinite set V ar of quantum variables. The symbols q, q ′ , q ′′ , q 0 , q 1 , q 2 , ... will be used as meta-variables ranging over quantum variables. Recall that in classical computation, we use a type to denote the domain of a variable. Thus, in quantum computation, a type should be the state space of a quantum system denoted by some quantum variable. Formally, a type t is a name of a Hilbert space H t . In this paper, we only consider two basic types: Boolean, integer. The results obtained in this paper can be easily generalized to the case with more types. The Hilbert spaces denoted by Boolean and integer are: Note that the sets denoted by types Boolean and integer in classical computation are exactly the computational bases of H Boolean and H integer , respectively (see Example 2.1). Now we assume that each quantum variable q has a type type(q), which is either Boolean or integer. The state space H q of a quantum variable q is the Hilbert space denoted by its type; that is, A quantum register is defined to be a finite sequence of distinct quantum variables. The state space of a quantum register q = q 1 , ..., q n is the tensor product of the state spaces of the quantum variables occurring in q; that is, Now we are able to define the syntax of quantum programs. The quantum programs considered in this paper are quantum extension of classical while-programs. Formally, they are generated by the following grammar: where • q is a quantum variable and q a quantum register; • U in the statement "q := U q"is a unitary operator on H q . In particular, if type(q) = integer, then the statement q := U +k q, where U +k is the k−translation operator, will be often abbreviated to q := q + k; • in the statement "measure M [q] : S", M = {M m } is a measurement on the state space H q of q, and S = {S m } is a set of quantum programs such that each outcome m of measurement M corresponds to S m ; The intuitive meaning of these quantum program constructs will become clear after introducing their operational semantics in the next section.
The following technical definition will be needed in the sequel.

Operational Semantics of Quantum Programs
We write H all for the tensor product of the state spaces of all quantum variables, that is, For simplicity of presentation, we will use E to denote the empty program. A quantum configuration is a pair S, ρ , where S is a quantum program or E, ρ ∈ D − (H all ) is a partial density operator on H all , and it is used to indicate the (global) state of quantum variables. Let q = q 1 , ..., q n be a quantum register. A linear operator A on H q has a cylinder extension on H all , where I V ar−{q} is the identity operator on the Hilbert space In the sequel, we will simply for A for its extension (1), and it can be easily recognized from the context, without any risk of confusion. The operational semantics of quantum program is defined to be a transition relation → between quantum configurations. By a transition S, ρ → S ′ , ρ ′ we mean that after executing quantum program S one step in state ρ, the state of quantum variables becomes ρ ′ , and S ′ is the remainder of S still to be executed. In particular, if S ′ = E, then S terminates in state ρ ′ . The transition relation → is given by the transition rules in Fig.1.
The meanings of various program constructs are precisely specified by the transitional rules in Fig.1. The statement "skip"does nothing and terminates immediately. The initialization "q := 0"sets quantum variable q to the basis state |0 . To see the role of initialization more clearly, we consider the case of type(q) = integer as an example. First, suppose ρ is a pure state; that is, ρ = |ψ ψ| for some |ψ ∈ H all . We can write |ψ in the form: where |ψ k is a product state, say After the initialization the state becomes: In general, suppose ρ is generated by an ensemble {(p i , |ψ i )} of pure states, that is, For each i, we write ρ i = |ψ i ψ i | and assume that it becomes ρ q i0 after the initialization. By the above argument, we can write ρ i0 in the form: where |ϕ ik ∈ H var−{q} for all k. Then the initialization makes that ρ becomes From Eqs. (2) and (3) we see that the state of q is set to be |0 and the states of the other quantum variables are unchanged. The statement "q := U q"simply means that unitary transformation U is performed on quantum register q, leaving the states of the quantum variables not in q unchanged. Remark that U in the target configuration of the rule (Unitary Transformation) stands indeed for the cylinder extension of U on H all (see Eq. (1)). A similar remark applies to the rules for measurements and loops. Sequential composition is similar to its counterpart in classical computation. The program construct "measure M [q] : S"is a quantum generalization of classical conditional statement. Recall that the first step of the execution of conditional statement "if B then S 1 else S 2 fi"is to check whether Boolean expression B is satisfied. However, according to a basic postulate of quantum mechanics, the unique way to acquire information about a quantum system is to perform a measurement on it. So, in executing the statement "measure M [q] : S", quantum measurement M will first be performed on quantum register q, and then a subprogram S m in S will be selected to be executed next according to the outcome of measurement. The essential difference between a measurement statement and a classical conditional statement is that the state of program variables is changed after performing the measurement in the former, whereas it is not changed after checking the Boolean expression in the latter. Note that the outcome m is observed with probability and after the measurement the state becomes So, a natural presentation of the Measurement rule is the probabilistic transition: However, we adopt Selinger's suggestion [19] of encoding both probability p m and density operator ρ m into partial density operator This allows us to give the Measurement rule in terms of ordinary transition. The statement "while M [q] = 1 do S"is a quantum generalization of classical loop "while B do S od". To acquire information about quantum register q, a measurement M is performed on it. The measurement M is a yes-no measurement with only two possible outcomes 0, 1. If the outcome 0 (no) is observed, then the program terminates, and if the outcome 1 (yes) occurs, then the program executes the subprogram S and continues. The only difference between a quantum loop and a classical loop is that checking the loop guard B in a classical loop does not change the state of program variables, but in a quantum loop the measurement outcomes 0 and 1 occur with probabilities: respectively, and the state becomes M 0 ρM † 0 from ρ when the outcome is 0, and it becomes M 1 ρM † 1 when the outcome is 1. Again, we adopt Selinger's suggestion so that the (Loop 0) and (Loop 1) rules can be stated as ordinary transitions instead of probabilistic transitions.
Let S be a quantum program and ρ ∈ D − (H). If S ′ , ρ ′ can be reached from S, ρ in n steps in the transition relation →; that is, there are configurations S 1 , ρ 1 , ..., S n−1 , ρ n−1 such that A transition sequence of S starting in ρ is a finite or infinite sequence of configurations in the following form: If it cannot be extended, then it is called a computation of S starting in ρ. Moveover, if it is finite and its last configuration is E, ρ ′ , then we say that it terminates in ρ ′ ; and if it is infinite, then we say that it diverges. We say that S can diverge from ρ whenever it has a diverging computation starting in ρ.
Classical while-programs are a typical class of deterministic programs that have exactly one computation starting in a given state. As shown in the following example, however, quantum while-programs no longer possess such a determinism because probabilism is introduced by the measurements in the statements "measure M [q] : S"and "while M [q] = 1 do S". After encoding probabilities into partial density operators, probabilism manifests as nondeterminism in transition rules (Measurement), (Loop 0) and (Loop 2).
Example 4.1 Suppose that type(q 1 ) = Boolean and type(q 2 ) = integer. Consider the program: Then the computations of S starting in ρ are: S, ρ → q 2 := 0; q 1 := Hq 1 ; q 2 := q 2 + 2; measure, ρ 1 → q 1 := Hq 1 ; q 2 := q 2 + 2; measure, ρ 2 where measure stands for the statement "measure M [q 1 ] : S", and So, S can diverge from ρ. Note that S 2 has also the transition but we always discard the transitions in which the partial density operator of the target configuration is zero operator.

Denotational Semantics of Quantum Programs
The denotational semantics of a quantum program is defined to be a semantic function which maps partial density operators to themselves. More precisely, for any quantum program S, the semantic function of S sums the computated results of all terminating computations of S. We write → * for the reflexive and transitive closures of →; that is, S, ρ → * S ′ , ρ ′ if and only if S, ρ → n S ′ , ρ ′ for some n ≥ 0.
Definition 5.1 Let S be a quantum program. Then its semantic function It should be pointed out that {| · |} in Eq. (4) stands for multi-set. The reason for using multi-sets is that the same density operator may be obtained through different computational paths as we can see from the measurement and loop rules in the operational semantics. The following simple example illustrates the case more explicitly. • S = S 0 , S 1 , S 0 = q := Iq and S 1 = q := σ x q.
Then the computation of S starting in ρ is given as follows: where measure is an abbreviation of "measure M [q] : S". So, we have: Now we are going to establish some basic properties of semantic functions. First, we prove its linearity.
, then for any quantum program S, we have: Proof. We can easily prove the following fact by induction on the structure of S: Then the conclusion immediately follows. Next we give a representation of semantic function [|S|] according to the structure of program S. To do this for quantum loops, we need some auxiliary notations. Let Ω be a quantum program such that [|Ω|] = 0 H all for all ρ ∈ D(H); for example, where q is a quantum variable, and is a trivial measurement on H q . We set: and if type(q) = integer, then Proof. (1), (2) and (3) are obvious.
(4) By Lemma 5.1 and the transitional rule for sequential composition we obtain: (5) follows immediately from the transitional rule for measurement.
(6) We introduce two auxiliary operators: for all ρ ∈ D − (H) and i = 0, 1. For simplicity, we write while for "while M [q] = 1 do S". First, we prove: for all n ≥ 1 by induction on n. The case of n = 1 is obvious. Then by (1), (4) and (5) and the induction hypothesis on n − 1 we obtain: Second, we have: So, it suffices to show that for all n ≥ 1. This can be easily done by induction on n.
If we only consider quantum variables of type Boolean, then the above proposition coincides with Fig.1 in [11]. However, it is worth noting that in [11] the denotational semantics of quantum programs was directly defined and it lacks a basis of operational semantics. Similar to Lemma 3.2 in [11], we may prove that the semantic function of a quantum program is a super-operator. Thus, the denotational semantics given in this section is consistent with Selinger's idea of modeling quantum programs as super-operators [19].
A recursive characterization of the semantic function of a quantum loop can be derived from the above proposition. Proof.Immediate from Proposition 5.1(6) and Eq. (5).
The following proposition shows that a semantic function does not increase the trace of density operator of quantum variables.    for all n ≥ 0. This can be carried out by induction on n. The case of n = 0 is obvious. By the induction hypothesis on n and S ′ , we have: From the proof of the above proposition, it is easy to see that the unique possibility that tr([|S|](ρ)) < tr(ρ) comes from the quantum loops occurring in S. Thus, tr(ρ) − tr([|S|](ρ)) is the probability that program S diverges from input state ρ. This can be further illustrated by the following example. For simplicity, we write while for this program. Let This means that program while terminates on input ρ with probability 1 2 , and it diverges from input ρ with probability 1 2 .
To conclude this section, we observe how quantum programs change the states of quantum variables and how they access quantum variables.
Let X ⊆ V ar be a set of quantum variables. For any A ∈ L(H all ), we write tr X (A) for tr N q∈X Hq (A). We put the long and dumb proof of the above proposition into the appendix.
Recall that tr X (ρ) describes the state of the quantum variables not in X when the global state of all quantum variables is ρ. So, Proposition 5.3 (1) indicates that the state of the quantum variables not in var(S) after implementing quantum program S is the same as that before implementing S. This means that program S can only change the state of quantum variables in var(S). On the other hand, Proposition 5.3 (2) shows that if two input states ρ 1 and ρ 2 coincide on the quantum variables in var(S), then the computed outcomes of S, starting in ρ 1 and ρ 2 , respectively, will also coincide on these quantum variables. In other words, program S can access at most the quantum variables in var(S).

Correctness Formulas
Correctness of a quantum program will be expressed by a quantum extension of Hoare triple in which a quantum predicate describes the input state and a quantum predicate describes the output states of the program. We adopt D'Hondt and Panangaden's definition of quantum predicates [10]. For any X ⊆ V ar, a quantum predicate on H X is defined to be a Hermitian operator P on H X such that We write P(H X ) for the set of quantum predicates on H X . Intuitively, for any ρ ∈ D − (H X ), tr(P ρ) stands for the probability that predicate P is satisfied in state ρ.
A correctness formula is a statement of the form:

{P }S{Q}
where S is a quantum program, and both P and Q are quantum predicates on H all . The quantum predicate P is called the precondition of the correctness formula and Q the postcondition. A correctness formula can be interpreted in two different ways: for all ρ ∈ D − (H).
The intuitive meaning of the defining inequality of total correctness is: the probability that input ρ satisfies quantum predicate P is not greater than the probability that quantum program S terminates on ρ and its output [|S|](ρ) satisfies quantum predicate Q. Recall that tr(ρ)−tr([|S|](ρ)) is the probability that quantum program S diverges from input ρ. Thus, the definition inequality of partial correctness means: if input ρ satisfies predicate P , then either program S terminates on it and its output [|S|](ρ) satisfies Q, or S diverges from it. The difference between total correctness and partial correctness is illustrated well by the following simple example.

Then it follows from linearity of [|S|] (Lemma 5.1) that
for all ρ ∈ D − (H all ).
Proof. Immediate from definition.

Weakest Preconditions and Weakest Liberal Preconditions
As in the case of classical Hoare logic, the notions of weakest precondition and weakest liberal precondition of quantum program will play a key role in establishing the (relative) completeness of Hoare logic for quantum programs. They may be defined in a familiar way: The next two propositions give explicit representations of weakest preconditions and weakest liberal preconditions, respectively. They will be used in the proof of completeness of quantum Hoare logic.
Proof. The trick is to simultaneously prove (1) and (2) by induction on the structure. This is indeed why we put these two conclusions that seem irrelevant at the first glance into a single proposition. Case 1. S = skip. Obvious. Case 2. S = q := 0. We only consider the case of type(q) = integer, and the case of type(q) = Boolean is similar. First, it holds that tr((  This claim can be proved by induction on n. The basis case of n = 0 is obvious. By the induction hypotheses on n and S ′ , we obtain: Proof. Similar to the case of weakest precondition, we prove (1) and (2) by induction on n, where (while) n is an abbreviation of (while M [q] = 1 do S ′ ) n . The case of n = 0 is obvious. By induction on S ′ and induction hypothesis on n, we observe: This completes the proof of Eq. (6). Note that quantum predicate P ⊑ I. Then I − P is positive, and by continuity of trace operator we obtain: For any Q ∈ P(H all ), |= par {Q}S{P } implies: for all ρ ∈ D − (H all ). This together with Lemma 2.1 leads to Q ⊑ ∞ n=0 P n . We see that Propositions 7.1 and 7.2 coincide with Figs. 2 and 3, respectively, in [11] when only quantum variables of type Boolean are considered. But Figs. 2 and 3 in [11] are given directly as definitions, and their intuitive meanings are not clear because they do not have any connection to total and partial correctness of quantum programs. In contrast, Propositions 7.1 and 7.2 fill in such a gap, and they are derived from Definition 7.1, which is given entirely based on the notions of total and partial correctness of quantum programs.
The next proposition gives a recursive characterization of weakest precondition and weakest liberal precondition of quantum loop, and it provides a key step in the proof of completeness of quantum Hoare logic. Proof. We only prove (2), and the proof of (1) is similar and easier. For every ρ ∈ D − (H all ), by Proposition 7.2(2) we observe:

Proof System for Partial Correctness
Now we are ready to present an axiomatic system of Hoare logic for quantum programs. The quantum Hoare logic can be divided into two proof systems, one for partial correctness and one for total correctness. In this section, we introduce the proof system qP D for partial correctness of quantum programs. It consists of the axioms and inference rules in Fig. 2.
We first prove the soundness of the proof system qP D with respect to the semantics of partial correctness: provability of a correctness formula in qP D implies its truth in the sense of partial correctness.
Theorem 8.1 (Soundness) The proof system qP D is sound for partial correctness of quantum programs; that is, for any quantum program S and quantum predicates P, Q ∈ P(H all ), we have: Proof. We only need to show that the axioms and inference rules of qP D are valid in the sense of partial correctness.
(Axiom Initialization) We only prove the case of type(q) = integer, and the case of type(q) = Boolean is similar. For any ρ ∈ D − (H all ), it follows from Proposition 5.1.2 that = tr(P [|q := 0|](ρ)). Therefore, we have: Furthermore, we have: for all n ≥ 1. In fact, Eq. (8) may be proved by induction on n. The case of n = 1 is obvious. Using Eq. (7), we obtain: Combining Eqs. (8) and (9), we assert that Therefore, Eq. (8) holds in the case of n + 1 provided it is true in the case of n, and we complete the proof of Eq. (8). Now we note that Then it follows that On the other hand, we have: Putting Eqs. (10) and (11) into Eq. (8), we obtain: Let n → ∞. Then it follows that and Now we are going to establish completeness for the proof system qP D with respect to the semantics of partial correctness: truth of a quantum program in the sense of partial correctness implies its provability in qP D. Note that the Löwner ordering assertions between quantum predicates in (Rule Order) are statements about complex numbers. So, only a completeness of qP D relative to the theory of the field of complex numbers may be anticipated; more precisely, we can add all statements that are true in the field of complex numbers into qP D in order to make it complete. The following theorem should be understood exactly in the sense of such a relative completeness. Theorem 8.2 (Completeness) The proof system qP D is complete for partial correctness of quantum programs; that is, for any quantum program S and quantum predicates P, Q ∈ P(H all ), we have: Proof. If |= par {P }S{Q}, then by Definition 7.1 (2) we have P ⊑ wlp.S.Q. Therefore, by (Rule Order) it suffices to prove the following: We proceed by induction on the structure of S. Case 1. S = skip. Immediate from (Axiom Skip). Case 2. S = q := 0. Immediate from (Axiom Initialization).

Proof System for Total Correctness
The aim of this section is to present a proof system qT D for correctness of quantum program. The only difference between qT D and qP D is the inference rule for quantum loops. To give the rule for total correctness of quantum loops, we need a notion of bound function which express the number of iterations of a quantum loop in its computation.
Recall that a bound function t of a classical loop "while B do S od "satisfies the inequality t([|S|](s)) < t(s) for any input state s. It is interesting to compare it with conditions (1) and (2) of the above definition, and we see that the latter are two inequalities between t([|S|](M 1 ρM † 1 )) and t(ρ) but not between t([|S|](ρ)) and t(ρ). This is because in the implementation of the quantum loop "while M [q] = 1 do S", we need to perform the yes-no measurement M on ρ when checking the loop guard "M [q] = 1", and the state of quantum variables will become M 1 ρM † 1 from ρ whence the measurement outcome "yes"is observed.
The following lemma gives a characterization of the existence of bound function of a quantum loop in terms of the limit of the state of quantum variables when the number of iterations of the loop goes to infinity. It provides a key step for the proof of soundness and completeness of the proof system qT D. Then it holds that tr(P ρ k ) ≥ ǫ 0 , and by conditions 1 and 2 in Definition 9.1 we obtain: Consequently, we have an infinitely descending chain {t ǫ 0 (ρ k )} in N, the set of nonnegative integers. This is a contradiction because N is a well-founded set. ( then for any ǫ > 0, there exists N ∈ N such that tr(P ([|S|] • E 1 ) n (ρ)) < ǫ for all n ≥ N . We define: Now it suffices to show that t ǫ is a (P, ǫ)−bound function of loop "while M [q] = 1 do S". To this end. we consider the following two cases: Case 1. tr(P ρ) ≥ ǫ. Suppose that t ǫ (ρ) = N . Then tr(P ρ) ≥ ǫ implies N ≥ 1. By the definition of t ǫ , we assert that Therefore, t ǫ ([|S|](M † 1 ρM 1 )) ≤ N − 1 < N = t ǫ (ρ). Case 2. tr(P ρ) < ǫ. Again, suppose that t ǫ (ρ) = N . Now we have the following two subcases: Subcase 2.1. N = 0. Then for all n ≥ 0, It is easy to see that t ǫ ([|S|](M 1 ρM † 1 )) = 0 = t ǫ (ρ). Subcase 2.2. n ≥ 1. We can derive that in the way of Case 1. Now we are ready to present the proof system qT D for total correctness of quantum programs. It consists of the axioms (Axiom Skip), (Axiom Initialization) and (Axiom Unitary Transformation) and inference rules (Rule Sequential Composition), (Rule Measurement) and (Rule Order) in Fig.2 as well as inference rule (Rule Loop Total) in Fig.3.
The remainder of this section will be devoted to establish soundness and completeness of qT D: provability of a correctness formula in qT D is equivalent to its truth in the sense of total correctness. Theorem 9.1 (Soundness) The proof system T D is sound for total correctness of quantum programs; that is, for any quantum program S and quantum predicates P, Q ∈ P(H all ), we have: Proof. It suffices to show that the axioms and inference rules of T D are valid in the sense of total correctness.
The proof for soundness of (Axiom Skip), (Axiom Initialization) and (Axiom Unitary Transformation) is similar to the case of partial correctness. ( We first prove the following inequality: by induction on n. It holds that So, Eq. (13) is correct for the base case of n = 0. Assume Eq. (13) is correct for the case of n = m. Then applying Eq. (12), we obtain: Therefore, Eq. (13) also holds for the case of n = M + 1. Now, since for any ǫ > 0, there exists M † 1 QM 1 , ǫ−bound function t ǫ of quantum loop "while M [q] = 1 do S", by Lemma 9.1 we have: = tr(P [|while M [q] = 1 do S|](ρ)).
Theorem 9.2 (Completeness) The proof system T D is complete for total correctness of quantum programs; that is, for any quantum program S and quantum predicates P, Q ∈ P(H all ), we have: Proof. Similar to the case of partial correctness, it suffices to prove the following: So, our aim is to derive that By the induction hypothesis on S ′ we get: First, by Propositions 7.1 (2) and 5.1 (6) we observe: Second, we consider the following infinite series of nonnegative real numbers: Since Q ⊑ I H all , it follows from Propositions 5.1 (6) and 5.2 that Therefore, the infinite series Eq. (16) (14), and we complete the proof.
It should be pointed out that the above theorem is merely a relative completeness of qT D with respect to the theory of the fields of complex numbers because except that (Rule Order) is employed in qT D, the existence of bound functions in (Rule Loop Total) is also a statement about complex numbers.

Conclusion
Based on D'Hondt and Panangaden's idea of representing quantum predicates by Hermitian operators and Selinger's idea of modeling quantum programs by superoperators, a full-fledged Hoare logic is developed for deterministic quantum programs, and its completeness relative to the theory of the field of complex numbers is proved in this paper.
An interesting problem for further studies is to find reasonable extensions of the quantum Hoare logic presented in this paper for bigger classes of quantum programs, including nondeterministic quantum programs [25], parallel and distributed quantum programs. Hopefully, they will serve as a logical foundation of various effective techniques for verification of these bigger classes of quantum programs.
Appendix: Proof of Proposition 5.3 (1) We proceed by induction on the structure of S. Case 1. S = skip. Obvious. Case 2. S = q := 0. We only consider the case of type(q) = integer, and the case of type(q) = Boolean is similar. It holds that Case 3. S = q := U q. If {|ψ i } is an orthonormal basis of H q , then {U † |ψ i } is also an orthonormal basis of H q . Consequently, = tr var(S) (ρ).